G. Шары и лузы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Полоска состоит из бесконечного числа клеток. Клетки пронумерованы, начиная с $$$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$$$ последовательных просеиваний?»

Входные данные

В первой строке записано два целых числа $$$n$$$ и $$$m$$$ — количество луз и количество вопросов соответственно ($$$1 \leq n, m \leq 10^5$$$).

В следующей строке записано $$$n$$$ целых чисел $$$a_1, \ldots, a_n$$$ — номера клеток с лузами ($$$0 \leq a_1 < \ldots < a_n \leq 10^9$$$).

Следующие $$$m$$$ строк описывают вопросы. $$$i$$$-я из этих строк содержит два целых числа $$$x_i$$$ и $$$k_i$$$ ($$$0 \leq x_i, k_i \leq 10^9$$$).

Выходные данные

Выведите $$$m$$$ чисел — ответы на вопросы в том же порядке, в котором они заданы на входе.

Пример
Входные данные
3 15
1 3 4
0 0
1 0
2 0
3 0
4 0
0 1
1 1
2 1
3 1
4 1
0 2
1 2
2 2
3 2
4 2
Выходные данные
0
1
2
3
4
0
2
5
6
7
0
5
8
9
10