Хомяк Шустрик получил в подарок от ёжика Шуршика необычный калькулятор. Изначально на экране калькулятора отображается число $$$A$$$.

В инструкции к калькулятору указано фиксированное число $$$M$$$. Все арифметические операции выполняются именно с этим числом. Кроме того, Шуршик загадал числа $$$N$$$ и $$$B$$$ и сообщил их Шустрику.

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

• Операция «+»: заменить текущее значение $$$A$$$ на $$$A + M$$$.
• Операция «-»: заменить текущее значение $$$A$$$ на $$$A - M$$$.
• Операция «*»: заменить текущее значение $$$A$$$ на $$$A \cdot M$$$.
• Операция «%»: заменить текущее значение $$$A$$$ на остаток от деления $$$A$$$ на $$$M$$$. После этой операции выполняется условие $$$0 \le A \lt M$$$.

После выполнения некоторой (возможно, нулевой) последовательности операций получится число $$$A'$$$.

Ёжику Шуршику стало интересно, сможет ли Шустрик получить такое число $$$A'$$$, что

$$$$$$ A' \equiv B \pmod N. $$$$$$

Иначе говоря, числа $$$A'$$$ и $$$B$$$ должны иметь одинаковые остатки при делении на $$$N$$$.

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

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

На линии монорельса находятся $$$n$$$ станций, пронумерованных по порядку от $$$1$$$ до $$$n$$$.

У каждой станции $$$i$$$ есть название $$$s_i$$$ — строка из не более 20 латинских букв. Каждая буква написана на отдельной табличке.

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

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

Формально за одну операцию вы можете выбрать два индекса $$$1 \le i, j \le n$$$, а также любую букву из строки $$$s_i$$$, и перенести эту букву в любое место строки $$$s_j$$$. Такая операция занимает $$$1 + |i - j|$$$ ценнейших единиц времени.

Например, если $$$s_i = \texttt{ab}$$$ и $$$s_j = \texttt{cd}$$$, то за одну операцию переноса буквы из $$$i$$$ в $$$j$$$ можно сделать:

• $$$s_i = \texttt{a}$$$; $$$s_j = \texttt{bcd}$$$ или $$$s_j = \texttt{cbd}$$$ или $$$s_j = \texttt{cdb}$$$.
• $$$s_i = \texttt{b}$$$; $$$s_j = \texttt{acd}$$$ или $$$s_j = \texttt{cad}$$$ или $$$s_j = \texttt{cda}$$$.

Обратите внимание, что в операции также разрешено выбирать $$$i = j$$$.

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

Здесь, $$$\operatorname{sorted}(s_i)$$$ обозначает отсортированную в алфавитном порядке строку $$$s_i$$$. Например, $$$\operatorname{sorted}(\texttt{abacaba}) = \texttt{aaaabbc}$$$.

Персик — акула в мире программирования — решил составить расписание для всех профилей олимпиады Innopolis Open.

В учебном году $$$D$$$ дней, пронумерованных от $$$1$$$ до $$$D$$$. Всего проводится $$$n$$$ олимпиад.

Олимпиады пронумерованы от $$$1$$$ до $$$n$$$ в порядке неубывания запланированной даты проведения. Каждая олимпиада проводится ровно в один день. Для каждой олимпиады известны её запланированная дата проведения и польза для подрастающего поколения.

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

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

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

Польза сезона равна сумме пользы всех $$$D$$$ дней.

Во благо школьников определите наибольшую возможную пользу сезона.

Тесты к этой задаче состоят из тринадцати групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых для неё групп.

Это интерактивная задача.

Кибер-акула Зубастик$$$^{\dagger}$$$ работает на складе и складывает коробки в одну вертикальную башню. Высота башни не ограничена, но акула может снимать с башни и класть на неё только верхнюю коробку. Также рядом есть буфер — свободная площадка, на которой можно временно держать коробки (в буфере может лежать любое количество коробок).

Коробки нумеруются в порядке прибытия, начиная с $$$1$$$. Для каждой коробки известен момент времени $$$t_j$$$, когда её нужно извлечь со склада.

В процессе работы происходят события двух типов:

• + t — пришла новая коробка, которую нужно извлечь в момент времени $$$t$$$ $$$(1 \le t \le T)$$$. Все значения $$$t$$$ различны.
• - j — наступил момент времени $$$t_j$$$, и требуется извлечь коробку с номером $$$j$$$.

Действия. Во время обработки события акула может выполнять следующие операции:

• 1 j — положить коробку $$$j$$$ на вершину башни (разрешено только если коробка $$$j$$$ лежит в буфере).
• 2 j — положить коробку $$$j$$$ в буфер (разрешено только если коробка $$$j$$$ лежит на вершине башни).

Правила обработки событий.

• При событии + t новая коробка сразу помещается в буфер. К концу обработки этого события буфер должен быть пустым.
• При событии - j к концу обработки этого события в буфере должна остаться ровно одна коробка — коробка $$$j$$$. После этого коробка $$$j$$$ считается извлечённой и удаляется из системы.

Ваша задача — для каждого события вывести набор операций, который корректно обработает это событие.

$$$^{\dagger}$$$ см. рис.

Кибер-акула Зубастик

Сначала ваша программа должна считать целое число $$$T$$$ — количество событий.

Затем для каждого $$$i = 1,2,\dots,T$$$ интерактор выводит строку с описанием события, происходящего в момент времени $$$i$$$:

• + t — пришла новая коробка, которую нужно извлечь в момент времени $$$t$$$ $$$(1 \le t \le T)$$$. Коробка получает следующий по порядку номер. К концу обработки события буфер должен быть пустым.
• - j — требуется извлечь коробку $$$j$$$. К концу обработки события в буфере должна остаться ровно одна коробка $$$j$$$.

После получения очередного события ваша программа должна вывести ответ для него в следующем формате:

• в первой строке целое число $$$K$$$ — количество операций для обработки текущего события;
• далее $$$K$$$ строк, в каждой две целых величины: тип операции ($$$1$$$ или $$$2$$$) и номер коробки $$$j$$$.

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

После вывода ответа обязательно сбросьте буфер вывода:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python.

Обратите внимание, что для более быстрой работы вывода стоит вызывать flush (или endl) после вывода всех $$$K$$$ операций, а не после каждой операции.

Интерактор в этой задаче не адаптивный: в рамках одного теста последовательность событий фиксирована и не меняется в зависимости от ваших ответов.

В этой задаче тесты двух видов.

Тест первого вида — генерируется массив [1, 1, 2, 2, ..., N, N] и случайным образом перемешивается, получается массив $$$[a_1, a_2, \dots, a_T]$$$ размера $$$T$$$, $$$T = 2N$$$. Тогда очередная коробка добавляется в момент времени $$$t_1$$$ и достаётся в момент времени $$$t_2$$$, если $$$t_1 \lt t_2$$$ и $$$a[t_1] = a[t_2]$$$.

Тест второго вида — гарантируется, что коробки достаются в том же порядке, в котором добавляются.

Для каждого значения $$$N$$$ (числа коробок) сгенерировано по одному тесту каждого вида.

Слон Филимон решил сьездить к знаменитой подруге панде из Китая города Чэнду с именем Чэн Ши. Чэн Ши очень любит бамбук и показала свою коллекцию бамбуковых надписей. Каждая надпись представляет собой строку из строчных латинских букв.

Коллекция Чэн Ши — это динамическое мультимножество строк. Изначально оно пусто.

Панда может выполнять операции двух типов:

• + s — добавить строку $$$s$$$ в мультимножество.
• - s — удалить одну копию строки $$$s$$$ из мультимножества.

Слону Филимону стало интересно какое наименьшее количество действий потребуется после каждой операции, чтобы все строки в текущем мультимножестве стали одинаковыми.

Разрешённые действия над одной строкой из коллекции:

1. Удаление последнего символа строки — Чэн Ши аккуратно откусывает кусочек бамбука.
2. Добавление любого символа в конец строки — панда сажает бамбук, и он вырастает, добавляя один символ в конец.

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

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

Помогите Чэн Ши быстро отвечать на вопрос Филимона после каждого изменения.

Александр и Бабин живут на заброшенном острове. Из развлечений у них есть только деревья, камни и бомбы (не спрашивайте откуда). Им очень скучно, и они хотят сыграть в игру. Александр предложил сыграть в «Сапёр», а Бабин — в «Ним». В качестве компромисса они решили сыграть в Нимсапёр!

Не имея выбора, в качестве игрового поля, ребята выбрали дерево. Напомним, что деревом называется связный неориентированный граф без циклов.

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

Бабин может прервать Александра после любого его хода. Как только это происходит, они начинают играть в «Ним» с получившимися кучками камней, причём Бабин ходит первым.

Если Бабин не прерывает Александра, Александр делает следующий ход (ставит ещё одну бомбу), после чего кучки камней обновляются, и так далее, пока Бабин не начнёт игру в «Ним».

Игрок, который не может сделать ход в «Ним», проигрывает.

Бабин очень хочет выиграть, поэтому он прервёт Александра в самый ранний возможный момент, когда сможет гарантировать свою победу.

Александр, хорошо понимая, что не может выиграть в этой игре, решил вместо этого максимизировать удовольствие, поэтому он хочет заложить как можно больше бомб, прежде чем Бабин начнёт игру в «Ним». Пожалуйста, помогите Александру найти максимальное количество бомб, которое он может заложить!

Напомним, что в игре «Ним» первый игрок выигрывает тогда и только тогда, когда побитовый XOR размеров кучек отличен от нуля.

Напомним, что XOR или Исключающим ИЛИ называется бинарная операция, которая так применяется к каждой паре битов, стоящих на одинаковых позициях в двоичных представлениях чисел, что в результате на этой позиции стоит 0, если биты равны, а иначе — 1. Например, 3 XOR 5 = 6, так как $$$3_{10}$$$ = $$$011_2$$$, $$$5_{10}$$$ = $$$101_2$$$ и потому после применения операции второй и третий бит становятся равными 1, а первый бит — 0, таким образом получается $$$110_2$$$ = $$$6_{10}$$$