математика

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

Как известно, любому таланту надо дать возможность реализоваться, поэтому мама Миши отправила сына на инновационную олимпиаду по ирригации (ИОИ). На этой олимпиаде школьники со всех концов Берляндии соревнуются в умении доставить воду для поливки растений самыми причудливыми способами. Зная список изобретений Миши, несложно догадаться, что проведение подобной олимпиады весьма затратно, поэтому спустя 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.

Примеры

№	Входные данные	Выходные данные
1	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
2	4 5 4 4 4 5 1 15 9 13 6	5 3 3 3

(с) Тимченко А., 2018 г.

Ни для кого не секрет, что Дед Мороз передвигается на особом транспортном средстве, принцип которого известен только самым приближенным зайцам Дедам Мороза. Однако, зайцы немного слабы в составлении маршрутов, и вам придется помочь им.

Принцип работы транспортного средства Деда Мороза(в дальнейшем ПепеЛАЦ(Пепе Летающий агрегат Цвайхандер)) такой:
на расстоянии одного километра друг от друга в точках (0, 0) и (1, 0) были построены две станции управления пепелацами A и B. С помощью них можно мгновенно переместить любой пепелац, повернув его на 90 градусов по или против часовой стрелки относительно точки A или B. Расстояние от пепелаца до соответствующей станции при этом не меняется. Следующее перемещение можно делать как относительно той же станции, так и относительно другой.

Например, если повернуть пепелац, находящийся в точке (3, 1) на 90 градусов против часовой стрелки относительно станции A, то он переместится в точку (−1, 3), если его затем повернуть на 90 градусов по часовой стрелке относительно станции B, то он переместится в точку (4, 2), если затем повернуть его вокруг станции B по часовой стрелке еще раз, он переместиться в точку (3, −3).
Деду Морозу необходимо добраться из точки (x1, y1) в точку (x2, y2). Помогите зайцам Деда Мороза составить маршрут, чтобы ему меньше пришлось ходить по заснеженному лесу.
Поскольку перемещения мгновенные и абсолютно бесплатные(магия же), то минимизировать количество перемещений не надо.

Формат входного файла
Входной файл содержит четыре целых числа — x1, y1, x2 и y2, они не превышают 104 по
абсолютной величине.

Формат выходного файла
Выведите в выходной файл последовательность перемещений с использованием станций управления, которая перемещает пепелац из точки (x1, y1) как можно ближе к точке (x2, y2).
Поворот по часовой стрелке относительно станции A обозначается как «+A», поворот против часовой стрелки относительно станции A обозначается как «-A», соответствующие повороты относительно станции B обозначаются как «+B» и «-B». Выводите по одному перемещению на строке. Выведенная последовательность не обязана быть минимальной по количеству перемещений, но должна содержать не более 106 действий.

Примеры

Ввод	Вывод
3 1 3 -3	-A    +B +B
0 0 3 0	-B +B

 (с) Павел Колодкин, 12И

Какая наука является первоисточником информатики?

1. математика
2. обществознание
3. кибернетика
4. теория информации

Появление новых свойств системы, которым не обладал ни один из ее элементов называется

1. системный эффект
2. результат объединения
3. бином системы
4. эффект бабочки

Какая концепция характеризует информацию как свойство саморганизующихся систем?

1. классическая
2. системная
3. коммуникационная
4. функциональная