D. Ирригация
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мальчика Мишу с юных лет волновали вопросы доставки воды. вот почему мама Миши отправила сына на ежегодную инновационную олимпиаду по ирригации (ИОИ). На этой олимпиаде школьники со всех концов Берляндии соревнуются в умении доставить воду для поливки растений самыми причудливыми способами. Проведение подобной олимпиады весьма затратно, поэтому спустя $$$n$$$ первых проведений олимпиады было решено ввести правило, по которому будет определяться место проведения соревнования в следующий год.

Город для проведения олимпиады выбирается следующим образом: всего в Берляндии есть $$$m$$$ городов, пронумерованных от $$$1$$$ до $$$m$$$, готовых принять соревнование. Каждый год олимпиада проводится в городе, в котором она проводилась наименьшее число раз. Если таких городов несколько, то олимпиада проводится в городе с наименьшим номером среди городов с минимальным числом проведений олимпиады.

Мишина мама очень волнуется за сына, поэтому её интересует, в каком городе будет проходить олимпиада в определённые годы. Единственная информация, которой располагает мама Миши, — места проведения олимпиады в первые $$$n$$$ лет. Помогите маме Миши, и она попросит Мишу не залить вашу квартиру.

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

В первой строке заданы три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$1 \leq n, m, q \leq 500\,000$$$) — количество проведений олимпиады до введения правила, количество городов в Берляндии, готовых провести олимпиаду, и число лет, про которые маму Миши интересует место проведения олимпиады, соответственно.

В следующей строке содержится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq m$$$), где $$$a_i$$$ — номер города, в котором проводилась олимпиада в год $$$i$$$. Обратите внимание, что до принятия правила место проведения олимпиады могло выбираться произвольным образом.

В следующих $$$q$$$ строках заданы целые числа $$$k_i$$$ ($$$n + 1 \leq k_i \leq 10^{18}$$$) — номера годов, для которых маму Миши интересует место проведения олимпиады.

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

Выведите $$$q$$$ целых чисел. В строке с номером $$$i$$$ выведите одно целое число — место проведения олимпиады в год $$$k_i$$$.

Примеры
Входные данные
6 4 10
3 1 1 1 2 2
7
8
9
10
11
12
13
14
15
16
Выходные данные
4
3
4
2
3
4
1
2
3
4
Входные данные
4 5 4
4 4 5 1
15
9
13
6
Выходные данные
5
3
3
3
Примечание

В первом примере Мишина мама интересуется о первых $$$10$$$ годах после принятия нового правила, в эти года олимпиада пройдёт в городах 4, 3, 4, 2, 3, 4, 1, 2, 3, 4.

Во втором примере после принятия нового правила олимпиада пройдёт в городах 2, 3, 1, 2, 3, 5, 1, 2, 3, 4, 5, 1.