Задача: Ирригация

Мальчика Мишу с юных лет волновали вопросы доставки воды. Когда Мише было четыре года, он приносил воду для полива растений в воздушных шариках вместо вёдер, так как воду в ведре было проще расплескать. Когда Мише исполнилось шесть лет, он построил в квартире водопровод из трубочек для сока, автоматизировав тем самым поливку цветов у себя в комнате. Все полученные в школе знания Миша сразу же использовал в своих смелых изобретениях: передача воды по проводам, насос из зубочисток, кран из маминого флакончика духов — вот далеко не полный список изобретений мальчика в школьные годы.

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

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

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

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

В следующих q строках заданы целые числа k_i (n+1 ≤ k_i ≤ 10¹⁸) — номера годов, для которых маму Миши интересует место проведения олимпиады.

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

Примеры

Ваш ответ: