Задача №114138. Ирригация
Мальчика Мишу с юных лет волновали вопросы доставки воды. Когда Мише было четыре года, он приносил воду для полива растений в воздушных шариках вместо вёдер, так как воду в ведре было проще расплескать. Когда Мише исполнилось шесть лет, он построил в квартире водопровод из трубочек для сока, автоматизировав тем самым поливку цветов у себя в комнате. Все полученные в школе знания Миша сразу же использовал в своих смелых изобретениях: передача воды по проводам, насос из зубочисток, кран из маминого флакончика духов — вот далеко не полный список изобретений мальчика в школьные годы.
Как известно, любому таланту надо дать возможность реализоваться, поэтому мама Миши отправила сына на инновационную олимпиаду по ирригации (ИОИ). На этой олимпиаде школьники со всех концов Берляндии соревнуются в умении доставить воду для поливки растений самыми причудливыми способами. Зная список изобретений Миши, несложно догадаться, что проведение подобной олимпиады весьма затратно, поэтому спустя \(n\) первых проведений олимпиады было решено ввести правило, по которому будет определяться место проведения соревнования в следующий год. Город для проведения олимпиады выбирается следующим образом: всего в Берляндии есть \(m\) городов, пронумерованных от \(1\) до \(m\), готовых принять соревнование. Каждый год олимпиада проводится в городе, в котором она проводилась наименьшее число раз. Если таких городов несколько, то олимпиада проводится в городе с наименьшим номером среди городов с минимальным числом проведений олимпиады.
Мишина мама очень волнуется за сына, поэтому её интересует, в каком городе будет проходить олимпиада в определённые годы. Единственная информация, которой располагает мама Миши, — места проведения олимпиады в первые \(n\) лет. Помогите маме Миши, и она попросит Мишу не залить вашу квартиру.
В первой строке заданы три целых числа \(n\), \(m\) и \(q\) (\(1 \leq n, m \leq 500\,000\), \(1 \leq q \leq 20\)) — количество проведений олимпиады до введения правила, количество городов в Берляндии, готовых провести олимпиаду, и число лет, про которые маму Миши интересует место проведения олимпиады, соответственно.
В следующей строке содержится \(n\) целых чисел \(a_i\) (\(1 \leq a_i \leq m\)) — номера городов, в которых проводилась олимпиада в год \(i\). Обратите внимание, что до принятия правила место проведения олимпиады могло выбираться произвольным образом.
В следующих \(q\) строках заданы целые числа \(k_i\) (\(n + 1 \leq k_i \leq 10^{18}\)) — номера годов, для которых маму Миши интересует место проведения олимпиады.
Выведите \(q\) целых чисел. В строке с номером \(i\) выведите одно целое число — место проведения олимпиады в год \(k_i\).
В первом примере Мишина мама интересуется о первых \(10\) годах после принятия нового правила, в эти года олимпиада пройдёт в городах 4, 3, 4, 2, 3, 4, 1, 2, 3, 4.
Во втором примере после принятия нового правила олимпиада пройдёт в городах 2, 3 , 1, 2, 3 , 5, 1, 2, 3 , 4, 5 , 1.
Данная задача состоит из \(50\) тестов, помимо тестов из условия. Каждый из них оценивается в \(2\) балла. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.
-
Решения, корректно работающие при \(n, m \leq 100\), \(k \leq 200\), наберут не менее \(20\) баллов.
-
Решения, корректно работающие при \(n, m \leq 100\), наберут не менее \(30\) баллов.
-
Решения, корректно работающие при \(n, m \leq 100\,000\), \(k \leq 250\,000\), наберут не менее \(40\) баллов.
-
Решения, корректно работающие при \(n, m \leq 100\,000\), наберут не менее \(70\) баллов.
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