Полный муравьев вертолет летит под ядерным дождем над кольцевой дорогой.

Дорога состоит из N клеток, пронумерованных от 1 до N по часовой стрелке. Изначально вертолет находится над клеткой 1, и из него в эту клетку десантируется первый муравей. Он начинает бежать по дороге по часовой стрелке, перемещаясь за одну минуту ровно на одну клетку. Через K минут муравей погибает, а в клетке, в которой он погиб, сразу же вырастает гриб. После гибели очередного муравья вертолет перемещается на следующую клетку по часовой стрелке (относительно своего положения) и высаживает в неё следующего муравья, который бежит аналогичным образом.

По дороге муравей съедает все грибы. При этом первый съеденный гриб позволяет ему пробежать дополнительно ⌊ K / 2⌋ (округление вниз) минут, второй — дополнительно ⌊ K / 3⌋ минут и т.д. Другими словами, если муравей съел всего P грибов, то он пробежит K + ⌊ K / 2⌋ + ⌊ K / 3⌋ + ... + ⌊ K / (P + 1)⌋ минут. Если муравей собирается погибнуть в клетке с грибом, он успевает его съесть. Таким образом, ни в какой клетке не может оказаться более одного гриба в один момент времени.

Если очередной муравей пробегает всю дорогу и возвращается в свою стартовую клетку, миссия считается выполненной, муравью присваивается звание героя и вертолет улетает. Необходимо определить номер муравья-героя или вывести  - 1, если вертолет будет кружить над дорогой вечно, при условии, что в вертолете изначально бесконечное количество муравьев.

В городе открылся магазин с фиксированной ценой P, в котором действуют следующие правила:

• если рыночная стоимость единицы товара S_i больше либо равна P, то одна единица товара продаётся по цене P;
• если рыночная стоимость единицы товара S_i меньше P, то товар продаётся только целыми упаковками ценой P, каждая из которых содержит ⌈ P / S_i⌉ (округление вверх) единиц товара.

Посчитайте для каждого из N товаров стоимость покупки не менее A_i единиц товара в магазине с фиксированной ценой.

Берляндская компания «Панические технологии» производит определенную стратегически важную продукцию. Единственный завод компании находится в городе $$$1$$$, из которого продукция доставляется во все остальные города на Белых поездах по железнодорожным путям.

Всего в Берляндии $$$N$$$ городов, некоторые из которых соединены ж/д путями. Города (вершины) и ж/д пути (ребра) образуют граф, который по необъяснимому стечению обстоятельств является вершинным кактусом — связным неориентированным графом, в котором каждая вершина лежит не более чем на одном простом цикле. Кроме того, длина всех циклов в этом графе четная.

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

Компания планирует построить еще $$$K$$$ заводов в некоторых городах, из которых продукция будет так же доставляться во все остальные города по тому же алгоритму. Чтобы сохранить гарантию отсутствия возможности столкновения между поездами, компании может потребоваться достроить дополнительные ж/д пути. По законам Берляндии между городами $$$A$$$ и $$$B$$$ разрешено строить новый ж/д путь только в том случае, если непосредственно между ними уже существует ж/д путь. Таким образом, компания решила достроить между некоторыми такими городами парный ж/д путь, предписывая поездам двигаться из $$$A$$$ в $$$B$$$ по одному из путей, а из $$$B$$$ в $$$A$$$ — по другому. В таком случае столкновения между этими городами никогда не произойдет.

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

Организаторы музыкального конкурса Евровидение устали от экспериментов участников и опубликовали новый свод правил, которому необходимо следовать при сочинении песен:

• длительность песни должна составлять ровно T секунд;
• куплеты, припев и проигрыши должны исполняться целиком без пауз;
• припев может быть исполнен сколько угодно раз (в том числе ноль), но каждый куплет и проигрыш — не более одного раза;
• куплеты, припев и проигрыши можно исполнять в любом порядке, но никакие два куплета не должны исполняться подряд.

Группа уже сочинила припев длительностью A и N проигрышей с длительностями S_i. Теперь группа планирует сочинить некоторое количество куплетов длительностью B, чтобы составить песню, удовлетворяющую всем правилам Евровидения. Какое минимальное количество куплетов ей необходимо сочинить?

Программист Пётр ненавидит сокращения. Его предшественник, напротив, считал, что код должен быть коротким, и активно пользовался сокращениями. К счастью, перед увольнением он составил словарь — список S, состоящий из N полных слов, которые он сокращал.

У Петра есть текст T, состоящий из M слов. Слово из текста T_i является сокращением слова из словаря S_j, если выполняются следующие условия:

• T_i является подпоследовательностью S_j, то есть слово T_i можно получить путём удаления нуля или более символов из слова S_j;
• не существует другого слова в словаре S_k (k ≠ j), для которого слово T_i являлось бы подпоследовательностью.

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

При подготовке задачи по программированию было разработано $$$N$$$ решений и измерено время работы $$$T_i$$$ каждого из них на самом худшем тесте.

Специальная строка $$$S$$$ длины $$$N$$$ описывает тип каждого решения: символ $$$S_i$$$ определяет тип решения номер $$$i$$$. При этом символ 0 соответствует плохому решению, ? — спорному, а 1 — хорошему.

Тайм-лимит $$$X$$$ считается корректным, если:

• время работы всех плохих решений превышает тайм-лимит как минимум в два раза ($$$T_i \ge X \times 2$$$, если $$$S_i = 0$$$);
• время работы всех хороших решений не превышает половину тайм-лимита ($$$T_i \le X / 2$$$, если $$$S_i = 1$$$).

Время работы спорных решений не влияет на корректность тайм-лимита.

Даны $$$Q$$$ запросов, каждый из который представляет собой строку $$$S$$$ длиной $$$N$$$, описывающую тип каждого решения. Найдите для каждого запроса минимальный целый положительный тайм-лимит, который считается корректным, или определите, что это невозможно.

Новогодняя гирлянда после включения загорается на $$$A$$$ минут, потом гаснет на $$$A$$$ минут, потом опять загорается на $$$A$$$ минут, гаснет на $$$A$$$, и так до бесконечности. Параметр $$$A$$$ задаётся пользователем перед первым включением гирлянды и может быть любым натуральным числом.

Детишки расстроятся, если во время праздников, которые начинаются в момент времени $$$0$$$ и заканчиваются в момент времени $$$T$$$, гирлянда будет гореть меньше половины времени.

В гости к детишкам на праздники приезжает дедушка, который не любит горящие гирлянды. Вам известны интервалы времени, в которые он будет присутствовать дома. Найдите такое значение параметра $$$A$$$ и время включения гирлянды, которые позволят минимизировать длительность времени нахождения дедушки дома с включенной гирляндой и при этом не приведут к расстройству детишек. Учтите, что включить гирлянду можно в любой целочисленный момент времени, в том числе до наступления праздников, но выключить её после включения уже нельзя.

Ученые Берляндии разработали новый передовой защищенный отечественный язык программирования LOCALC++. В целом, этот язык является клоном языка C++ с той лишь разницей, что в LOCALC++ числа выводятся в консоль с разделителями.

В данной задаче рассматриваются только неотрицательные целые числа. При выводе число разбивается на группы из трех цифр, начиная с младших разрядов, и каждая группа отделяется пробелом. Например, число $$$178489$$$ будет выведено в виде $$$178\ 489$$$, число $$$17009$$$ в виде $$$17\ 009$$$, а число $$$5$$$ будет выведено в таком же виде.

Программа управления атомными электростанциями Берляндии, написанная на LOCALC++, вывела в лог очень важную статистику в виде набора чисел через пробел. Известно, что исходные числа были строго меньше $$$10^K$$$. Необходимо определить количество различных наборов чисел, вывод которых бы привел к такому же логу.

Пока Рик в очередной раз спасал вселенную исключительно в своих интересах, Морти нашел в гараже набор разноцветных плюмбусов, развешенных на веревке.

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

Всего на веревке $$$N \times K$$$ плюмбусов: по $$$N$$$ штук каждого из $$$K$$$ цветов. За одну секунду Морти может снять любой плюмбус и повесить его с левого или с правого края веревки, то есть левее или правее всех остальных. Морти хочет получить такое расположение плюмбусов, при котором все плюмбусы одного цвета формируют ровно одну последовательную группу. В итоге на веревке будет $$$K$$$ таких групп. Последовательность групп при этом не имеет значения.

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

В сафари-парке Вася увидел двух крокодилов, которых кормили туристы. Заметив, что один из крокодилов сильнее другого и съедает больше мяса, он решил восстановить справедливость.

Для того чтобы покормить крокодилов, Вася купил цельный кусок мяса весом N килограммов. Он решил разрезать его на равное количество кусков размерами A и B килограммов, причём так, чтобы ничего лишнего не осталось. Вася планирует каждые K секунд бросать крокодилам один кусок мяса, чередуя размеры кусков. Самым первым он бросит кусок размером A.

Крокодилы едят мясо по следующим правилам:

• если крокодил не занят поеданием схваченного ранее куска мяса, и бросается новый кусок, то он пытается его схватить;
• если только один крокодил пытается схватить кусок, то он достаётся ему;
• если оба крокодила одновременно пытаются схватить кусок, то он достаётся сильному крокодилу;
• если кусок мяса не попытался схватить ни один крокодил, то он сразу тонет и не достаётся никому;
• если крокодил заканчивает поедание ранее схваченного куска одновременно с бросанием нового, он будет пытаться его схватить.

Помогите Васе найти такие целые положительные A и B, чтобы модуль разности количества съеденного крокодилами мяса был минимальным. Учтите, что скорость поедания мяса каждым крокодилом составляет один килограмм в секунду.