B. Лягушка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

По кругу расположены N камней, пронумерованных от 0 до N - 1 в направлении по часовой стрелке. На i-ом камне написано число ai.

Лягушка OSFrog начинает своё путешествие с камня под номером x и хочет совершить h прыжков. На j-ом прыжке (0 ≤ j ≤ h - 1), находясь на i-ом камне, она прыгает на ai камней по или против часовой стрелки. Направление определяется следующим образом: если количество единиц в двоичной записи j чётно, то она прыгает по часовой, иначе — против.

Дано M запросов с изначальным положением лягушки и количеством прыжков, которое она совершит. Определите номер камня, на котором она закончит прыжки.

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

В первой строке содержится целое число N — количество камней (1 ≤ N ≤ 2 × 105).

Во второй строке содержатся N целых чисел ai, написанных на камнях (0 ≤ ai ≤ 109).

В третьей строке содержится целое число M — количество запросов (1 ≤ M ≤ 2 × 105).

В следующих M строках содержатся запросы в виде пары чисел xk и hk (0 ≤ xk ≤ N - 1;0 ≤ hk ≤ 109).

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

Для каждого запроса в отдельной строке выведите номер камня, на котором лягушка закончит путешествие.

Примеры
Входные данные
5
1 4 2 5 3
4
0 1
0 2
2 3
3 100
Выходные данные
1
2
2
3