Блэку был ниспослан Священный массив \(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\)-го шага трансформации.
Выходные данные
Для каждого набора входных данных выведите \(q\) ответов. \(i\)-м ответом будет являться значение \(a_{x_i}\) после \(k_i\)-го шага трансформации. Можно показать, что ответ на каждый запрос единственен.
Примечание
Первый набор входных данных рассмотрен в условии задачи. Можно видеть, что:
- \(k_1 = 0\) (начальный массив): \(a_3 = 1\);
- \(k_2 = 1\) (после \(1\)-го шага): \(a_1 = 2\);
- \(k_3 = 2\) (после \(2\)-го шага): \(a_2 = 3\);
- \(k_4 = 1\) (после \(1\)-го шага): \(a_6 = 3\).
Для второго набора входных данных,
| Первоначальный массив: | \(1\) \(1\) |
| После \(1\)-го шага: | \(2\) \(2\) |
| После \(2\)-го шага: | \(2\) \(2\) |
| ... | ... |
Можно видеть, что:
- \(k_1 = 0\) (начальный массив): \(a_1 = 1\);
- \(k_2 = 1000000000\): \(a_2 = 2\);
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|