Полоска состоит из бесконечного числа клеток. Клетки пронумерованы, начиная с \(0\). Изначально в клетке \(i\) лежит шар с номером \(i\).
В \(n\) клетках \(a_1, \ldots, a_n\) расположены лузы. Каждая клетка содержит не более одной лузы.
Просеивание заключается в следующей последовательности операций:
- Лузы в клетках \(a_1, \ldots, a_n\) одновременно открываются, и шары, которые находятся в этих клетках, пропадают. После того, как шары пропали, лузы закрываются обратно.
- Для каждой клетки \(i\) от \(0\) до \(\infty\), происходит следующее: если в клетке \(i\) находится шар, мы перемещаем этот шар в свободную клетку \(j\) с минимальным номером. Если не существует свободной клетки \(j < i\), шар остается в клетке \(i\).
Обратите внимание, что после просеивания в каждой клетке снова будет находиться ровно по одному шару.
Рассмотрим пример: пускай лузы находятся в клетках \(1\), \(3\) и \(4\). Изначальное расположение шаров изображено внизу (в подчеркнутых позициях находятся лузы):
0 1 2 3 4 5 6 7 8 9 ... После открытия и закрытия луз шары 1, 3 и 4 исчезают:
0 2 5 6 7 8 9 ... После сдвига всех шаров влево конфигурация выглядит так:
0 2 5 6 7 8 9 10 11 12 ... После еще одного полного просеивания получится следующее:
0 5 8 9 10 11 12 13 14 15 ... Вам требуется ответить на \(m\) вопросов. \(i\)-й из этих вопросов выглядит так: «каков номер шара, который окажется в клетке \(x_i\) после \(k_i\) последовательных просеиваний?»