Недавно специальная комиссия, исследовав старую ханойскую башню, признала её аварийной и постановила снести. Но после пожара в Нотр-Дам де Пари и в память о столетней колонизации было решено подарить ханойскую башню французам для замены сгоревшего шпиля. Тем более, что транспортировка башни во Францию дешевле, чем утилизационный сбор.

Перевозить башню будут в разобранном виде по железной дороге, по одному диску на одной платформе. Специально для этого на каждой платформе установили стержень как у оригинальной башни. Но чтобы неопытные французские рабочие случайно не собрали башню в неправильном порядке, нужно разложить диски по платформам так, чтобы можно было собирать диски в башню в порядке их прибытия к месту назначения. То есть нижние диски должны быть ближе к голове состава, чем верхние.

Времени до отправления поезда осталось мало. А башня всё ещё находится в собранном виде на начальном стержне рядом с хвостом состава, меньшие диски лежат на больших. За один раз можно перемещать один диск либо на соседний стержень, либо через один стержень, вперёд или назад (включая начальный стержень). Диски большего диаметра нельзя класть на диски меньшего диаметра. Перемещать можно только те диски, на которых перед этим не лежат другие диски.

Зная, что в центральном регионе NEERC лучше всех умеют перемещать ханойские башни, вас просят разработать алгоритм для укладки башни из N дисков на состав из N платформ не более чем за T перекладываний.

Семен решил начать бегать по утрам. Но не каждый день, а через день. За день отдыха он как раз успевает соскучиться по бегу, так что ни в коем случае не пропустит тренировку. Правда, если он будет бегать два дня подряд, то ему это занятие наскучит, и он его бросит насовсем.

Чтобы не забыть, когда у него тренировки, он решил бегать по нечетным дням месяца. Конечно, это так себе план. Вам надо определить дату, когда он бросит тренировки. Такой датой будет первое четное число, следующее за второй пробежкой подряд.

После долгих лет войны с арахнидами человечество нашло возможность нанести разящий удар. Последние удачи военной разведки указали на логово королевы арахнидов, и вот вы уже на планете насекомоподобных со своим отрядом перед разрытыми норами, ведущими в сложную систему вражеских тоннелей и залов. Ситуация усугубляется тем, что у вас нет никакого плана этой системы. Однако вы знаете, что таких залов не больше $$$10^5$$$ и королева находится в зале с номером $$$9999$$$.

Вы находитесь в зале номер 0 и снаряжаете несколько дронов, которых запускаете во все входы, к которым имеете доступ. Дроны должны исследовать всю систему и дать вам возможность спланировать ваш удар. Каждый дрон время от времени выходит с вами на связь и передает информацию о переходах между залами. Несмотря на то, что человеческая мысль позволила сделать дроны невидимыми для арахнидов, глубина залегания пещер такова, что какая-то часть данных теряется в помехах. Поэтому дроны передают информацию весьма фрагментарно.

Как только вы обнаруживаете, что дроны передали достаточно данных о том, чтобы построить маршрут между вами и залом, в котором находится королева, вы должны дать сигнал к атаке.

Если вдруг вы пропустите момент, когда маршрут может быть построен, а вы не отдали команду об атаке, вы сразу же попадаете под трибунал как пособник арахнидов.

Спланируйте успешную атаку и не попадите под трибунал.

Для чтения данных программа должна использовать стандартный ввод и осуществлять печать на стандартный вывод.

В начале работы программы в первой строке подается число $$$N$$$ ($$$0 \lt N \lt 10^5-1$$$), которое задает, что в начале вы имеете доступ к входам в залы $$$0, 1, 2,\ldots, N$$$.

Далее ваша программа будет получать со стандартного ввода данные от дронов. Каждая порция данных располагается в отдельной строке.

Первая порция данных от дронов будет доступна сразу же, а каждая последующая — только после того, как ваша программа вывела ваше текущее решение и выполнила операцию flush.

Первым передается целое число $$$K$$$ ($$$1\leqslant K\leqslant 42$$$), которое задает количество переходов. После него через пробел идут пары чисел $$$0\leqslant f_i, t_i \lt 10^5$$$, которые задают, что дронами был обнаружен переход между залами с номерами $$$f_i$$$ и $$$t_i$$$.

После получения каждой порции данных вам надо выдать «WAIT», если вы не видите пути от вашего местоположения к королеве, и тогда дроны продолжат свою работу, либо «ATTACK», если вы можете построить такой путь и надо атаковать. Указанные команды выводятся в отдельной строке на стандартный вывод. После вывода команды «ATTACK» ваша программа должна завершить свою работу.

Одним из первых уроков, который выносит начинающий трейдер, является понимание того, что если в первый день его вложения выросли на 50%, а во второй упали на 40%, то это не значит, что в итоге он заработал 10%, на самом деле он потерял 10%.

У вас есть исторические данные об изменениях цен на интересующий вас актив. Изменения цен измеряются в базисных пунктах. Один базисный пункт составляет 1/100 процента. Гарантируется, что хотя бы одно такое измерение будет положительным.

Вашей задачей будет обнаружить период, за который была самая большая доходность по данному активу. Доходность определяется как разница между стоимостью продажи актива в конце периода и стоимостью покупки актива в начале периода. Если периодов с одинаковой доходностью несколько, то надо вывести наиболее поздний из них. Более поздним из двух считается тот период, начало которого больше, если таких несколько, то тот, длина которого больше.

Петя выписал все натуральные числа от 1 до $$$N$$$ в следующем порядке: сначала в порядке возрастания все числа с суммой цифр 1, затем – с суммой цифр 2, затем – 3, и т.д. Какое число окажется на месте с номером $$$M$$$?

Одним из самых драматичных событий прошедшей зимней олимпиады стали положительные допинг-тесты бобслеистов. Конечно, на Родине все знают, что спортсменам просто нужно было подлечиться утром перед стартом. Но как теперь это объяснить инспекторам WADA? После этого инцидента лучшие учёные напряглись, освоили миллиардный грант и предложили новое трёхкомпонентное средство: можно взять кексики с маком, кокосовую пудру, с феном всё это разогреть и использовать за час до старта.

Для того чтобы средство получилось максимально эффективным, но в то же время не причинило вред, характеристики его компонентов должны удовлетворять секретному неравенству: $$$$$$ 0 \le c - \left( a \oplus b \oplus \left\lfloor \dfrac{a}{b} \right\rfloor \oplus \left\lfloor \dfrac{b}{a} \right\rfloor \oplus \left\lfloor \dfrac{a \oplus b}{a} \right\rfloor \oplus \left\lfloor \dfrac{a \oplus b}{b} \right\rfloor \right) \lt D, $$$$$$ где $$$a$$$ – характеристика кексиков (время выпекания), $$$b$$$ – характеристика кокосовой пудры (размер помола), $$$c$$$ – характеристика фена (мощность), $$$D$$$ – допустимая погрешность, $$$\oplus$$$ – побитовое исключающее «или», $$$\lfloor \cdot \rfloor$$$ – целая часть числа.

Конечно же, спортивные власти будут постоянно запрещать обнаруженное средство. Поэтому необходимо как можно чаще менять характеристики его компонентов так, чтобы при этом секретное неравенство по-прежнему выполнялось.

Вам дано число $$$D$$$ и характеристики всех компонентов, имеющихся в распоряжении сборной по бобслею. Определите, сколько существует различных способов из имеющихся компонентов получить средство, удовлетворяющее секретному неравенству.

После повсеместного распространения искусственного интеллекта Комиссия по защите прав роботов постановила размещать в общественных местах наряду с традиционными часами электронные циферблаты, показывающие время в удобном для робота формате.

Циферблат, который нравится роботу, отображает таймстапм — количество полных секунд, прошедших с некоторого момента времени. Каждую секунду значение таймстапма на циферблате увеличивается на 1. Известно, что дисплеи подобных циферблатов имеют ширину 10 цифр, а каждая цифра написана почтовым шрифтом - как индекс на оставшихся разве что в музее Почты России конвертах.

     _   _       _   _   _   _   _   _ 
  |  _|  _| |_| |_  |_    | |_| |_| | |
  | |_   _|   |  _| |_|   | |_|  _| |_|

Чтобы отображать цифры, используются светодиодные элементы постоянной мощности. Так, например, чтобы обеспечить отображение на циферблате цифры «1» в течение одной секунды, требуется 2 единицы энергии, для цифры «8» придется потратить 7 единиц энергии. Сразу после включения часов на циферблате загораются 10 нулей, и далее значение таймстапма всегда отображается с ведущими нулями.

Требуется посчитать количество единиц энергии, которое затратят часы в течение $$$N$$$ секунд после включения.

Мало кто знает, но у Уильяма Роуэна Гамильтона был слон Тирион. Он часто любил гулять по странным объектам, которые в жизни не встречаются. Одним из таких объектов был Гамильтонов сад. В Гамильтоновом саду есть $$$13 \cdot n + 113$$$ растений, каждое из которых хочет увидеть Тирион. Расстояние между растениями определяется по следующему правилу: расстояние при переходе от растения с номером $$$i$$$ к растению с номером $$$j$$$ равно $$$(i - j)$$$ mod $$$n$$$ (растения нумеруются с единицы). Тирион хоть и любит гулять, но двигается он очень медленно. Именно поэтому он просит вас составить ему маршрут с кратчайшим суммарным расстоянием, который проходит по всем вершинам ровно один раз и возвращается в стартовую.

Темная ночь. Шумят волны, начинает капать дождь. Челкаш после очередного заплыва приплыл к контрабандистам, чтобы сбыть награбленный товар. Однако не все пошло по плану: выяснилось, что у контрабандистов на корабле уже фактически нет места. Задачу о рюкзаке контрабандисты не знают, и потому они требуют, чтобы Челкаш отдавал им товар в порядке неубывания веса. Челкаш уже очень устал и ничего не соображает, и потому эта задача кажется ему непосильной.

К его счастью, в этот раз он приплыл не один, а вместе с Гаврилой. Но запуганный Гаврила сидит в углу лодки и еле может пошевелить руками, и потому отсортировать товар он также не может. Поэтому Челкаш решает поступить так: он выкладывает весь товар в ряд и q раз меняет какие-то два элемента ряда местами. После этого он бросается на Гаврилу и требует, что бы он сказал, является ряд отсортированным по неубыванию или нет. Как уже было сказано, Челкаш очень устал, и даже если в какой-то момент товар оказался отсортированным, Челкаш может продолжить задавать вопросы.

В темноте Гаврила видит очень плохо, и потому он не может помочь своему товарищу. Но в то же время он понимает, что если он ошибется, то на следующий день, когда Челкаш узнает об ошибке, Гавриле несдобровать. Гаврила просит Вас помочь ему справиться со столь непростой задачей.

Коровьев (или Фагот) — старший подчинённый Воланда. Поэтому ему вместе с котом Бегемотом часто приходится выполнять поручения мессира. Но, кажется, на этот раз им не обойтись без Вашей помощи!

Воланд раздобыл карту города и хочет попасть в театр, где он будет демонстрировать сеансы чёрной магии с её полным разоблачением. На карте отмечены точки (дома), и их соединяют дороги. На дорогах написаны их протяжённости. Свита Воланда сейчас находится в одном из домов, отмеченных на карте. Театр тоже отмечен на карте.

Воланд попросил Коровьева и Бегемота разработать самый короткий маршрут от дома до театра. Но не всё так просто, ведь Воланд — не обычный смертный и обладает сверхспособностями. Поэтому он считает длиной маршрута побитовый OR длин дорог на этом маршруте (о том, что такое побитовый OR читайте в примечании).

Коровьев и Бегемот сами не справятся с такой сложной задачей, ведь на карте очень много домов и дорог. Они обратились за помощью к Вам. Помогите им! Напишите программу, которая будет решать эту задачу.