B. Священный массив
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Блэку был ниспослан Священный массив $$$a$$$ состоящий из $$$n$$$ ($$$1 \le n \le 2000$$$) целых чисел. У каждого элемента $$$a$$$ есть первоначальное состояние. Однако после ругательств в свою сторону, массив разозлился и начал бесконтрольно трансформироваться.

Трансформация состоит из бесконечного количества шагов. На $$$i$$$-м шаге массив $$$a$$$ меняется следующим образом: в каждой позиции $$$j$$$, $$$a_j$$$ становится равным количеству вхождений значения $$$a_j$$$ в $$$a$$$ перед началом этого шага.

Для большего понимания, ниже приведен пример превращения:

Первоначальный массив:$$$2$$$ $$$1$$$ $$$1$$$ $$$4$$$ $$$3$$$ $$$1$$$ $$$2$$$
После $$$1$$$-го шага:$$$2$$$ $$$3$$$ $$$3$$$ $$$1$$$ $$$1$$$ $$$3$$$ $$$2$$$
После $$$2$$$-го шага:$$$2$$$ $$$3$$$ $$$3$$$ $$$2$$$ $$$2$$$ $$$3$$$ $$$2$$$
После $$$3$$$-го шага:$$$4$$$ $$$3$$$ $$$3$$$ $$$4$$$ $$$4$$$ $$$3$$$ $$$4$$$
......

В первоначальном массиве были две $$$2$$$, три $$$1$$$, одна $$$4$$$ и одна $$$3$$$, а потому после первого шага, каждый элемент стал равен его количеству вхождений: все двойки стали равны $$$2$$$, все единицы стали равны $$$3$$$, четверка стала равна $$$1$$$ и тройка стала равна $$$1$$$.

Количество шагов в трансформации бесконечно.

Вам нужно обработать $$$q$$$ запросов: в каждом запросе Блэка интересует значение $$$a_x$$$ после $$$k$$$-го шага трансформации.

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

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следуют сами наборы входных данных.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$1 \le n \le 2000$$$) — размер массива $$$a$$$.

Во второй строке каждого набора заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — первоначальные значения массива $$$a$$$.

В третьей строке каждого набора задано одно целое число $$$q$$$ ($$$1 \le q \le 100\,000$$$) — количество запросов.

В следующих $$$q$$$ строках заданы сами запросы — по одному в строке. В $$$i$$$-й строке заданы два целых числа $$$x_i$$$ и $$$k_i$$$ ($$$1 \le x_i \le n$$$; $$$0 \le k_i \le 10^9$$$) означающих, что Блэка интересует значение $$$a_{x_i}$$$ после $$$k_i$$$-го шага трансформации. $$$k_i = 0$$$ означает, что Блэка интересуют значения первоначального массива.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$, а сумма $$$q$$$ по всем наборам не превосходит $$$100\,000$$$.

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

Для каждого набора входных данных выведите $$$q$$$ ответов. $$$i$$$-м ответом будет являться значение $$$a_{x_i}$$$ после $$$k_i$$$-го шага трансформации. Можно показать, что ответ на каждый запрос единственен.

Пример
Входные данные
2
7
2 1 1 4 3 1 2
4
3 0
1 1
2 2
6 1
2
1 1
2
1 0
2 1000000000
Выходные данные
1
2
3
3
1
2
Примечание

Первый набор входных данных рассмотрен в условии задачи. Можно видеть, что:

  1. $$$k_1 = 0$$$ (начальный массив): $$$a_3 = 1$$$;
  2. $$$k_2 = 1$$$ (после $$$1$$$-го шага): $$$a_1 = 2$$$;
  3. $$$k_3 = 2$$$ (после $$$2$$$-го шага): $$$a_2 = 3$$$;
  4. $$$k_4 = 1$$$ (после $$$1$$$-го шага): $$$a_6 = 3$$$.

Для второго набора входных данных,

Первоначальный массив:$$$1$$$ $$$1$$$
После $$$1$$$-го шага:$$$2$$$ $$$2$$$
После $$$2$$$-го шага:$$$2$$$ $$$2$$$
......

Можно видеть, что:

  1. $$$k_1 = 0$$$ (начальный массив): $$$a_1 = 1$$$;
  2. $$$k_2 = 1000000000$$$: $$$a_2 = 2$$$;