Чтобы попасть в заброшенный дом, в котором прячется Оно, ребятам нужно открыть дверь с хитроумным замком. Этот замок представляет собой дерево из $$$n$$$ вершин, каждая из которых покрашена в белый или черный цвет. Чтобы открыть замок, нужно уничтожить все вершины этого дерева. Для этого ребята могут выполнять две операции:

1. Перекрасить еще не уничтоженную вершину из белого в черный, или из черного в белый.
2. Запустить цепную реакцию, уничтожающую группу связных вершин одного цвета. Формально, ребята могут выбрать любую еще не уничтоженную вершину цвета $$$c$$$, уничтожить ее и все вершины цвета $$$c$$$, достижимые из нее по еще не уничтоженным вершинам цвета $$$c$$$.

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

Джокер известен своей безумностью. Именно из-за нее он использует систему счисления с основанием $$$a$$$, в которой все числа состоят из цифр от $$$0$$$ до $$$a - 1$$$. Также Джокер очень любит танцевать. Он может танцевать очень долго, поэтому он придумал для себя правило, которое не даст ему танцевать бесконечно. Конечно же, правило тоже странное: когда Джокер танцует, каждую секунду, начиная с первой, он произносит вслух число секунд, прошедшее с начала танца (разумеется, он произносит это число в $$$a$$$-ичной системе счисления), без ведущих нулей. Например, если $$$a = 3$$$, первые пять чисел, которые произнесет Джокер, будут следующими:

• Спустя секунду после начала: $$$1$$$
• Спустя две секунды после начала: $$$2$$$
• Спустя три секунды после начала: $$$10$$$
• Спустя четыре секунды после начала: $$$11$$$
• Спустя пять секунд после начала: $$$12$$$

Джокер выбрал массив $$$b_i$$$, состоящий из $$$a$$$ целых неотрицательных чисел, и решил останавливать свой танец, если после очередного произнесенного числа, он, за все время танца, ровно $$$b_i$$$ раз произнес цифру $$$i$$$ для всех $$$0 \le i \lt a$$$. Помогите ему определить, сколько секунд будет длиться его танец, или же сообщите, что он будет танцевать вечно.

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

Заклятье описывается двумы натуральными числами $$$a$$$ и $$$b$$$. Процесс снятия заклятья происходит следующим образом:

1. Перемножить числа от $$$a$$$ до $$$b$$$ включительно
2. Взять сумму цифр полученного числа
3. Если результат не меньше $$$10$$$, вернуться к пункту $$$2$$$

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

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

На кодовом замке написано $$$n$$$ натуральных чисел $$$a_1, a_2, \ldots, a_n$$$. И чтобы открыть его, нужно найти размер наибольшего подмножества этих чисел, что НОД чисел в подмножестве строго больше единицы. НОД множества чисел — это наибольшее натуральное число, делящее все числа из множества.

Помогите героям справиться с этой задачей!

У Авроры есть $$$n$$$ кубиков. У каждого кубика есть шесть сторон, на каждой из которых написана цифра от $$$0$$$ до $$$9$$$. Цифры на одном кубике могут повторяться.

Феи решили научить Аврору арифметике, и дали задание — собирать из кубиков числа. Аврора может выбрать произвольный набор кубиков, повернуть каждый кубик из набора произвольной стороной вверх и расставить их в произвольном порядке, чтобы получить желаемое число. Конечно же, Аврора собирает число без ведущих нулей.

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

У Джокера есть дерево, в котором он выбрал $$$m$$$ простых путей: $$$(u_1, v_1)$$$, $$$(u_2, v_2)$$$, $$$\ldots$$$, $$$(u_m, v_m)$$$ — каждый путь задается двумя вершинами $$$u_i$$$ и $$$v_i$$$, лежащими на его концах. Причем все пути имеют ненулевую длину, то есть $$$u_i \neq v_i$$$.

Теперь Джокер хочет расставить на ребрах дерева веса — целые числа $$$0$$$ или $$$1$$$. Обозначим $$$s_i$$$ сумму весов ребер на $$$i$$$-м пути по модулю $$$2$$$ (иначе говоря, исключающее ИЛИ весов всех ребер на этом пути). Джокер называет расстановку весов на ребрах безумной, если выполняется неравенство $$$s_{i} \le s_{i+1}$$$ для всех $$$1 \le i \lt m$$$.

Ваша задача — посчитать количество безумных расстановок весов на ребрах. Так как Джокер сумашедший, он попросил вас найти остаток от деления этого числа на $$$998\,244\,353$$$.

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

Сейчас они строят прямоугольную часть дороги размерами $$$n$$$ на $$$m$$$ метров. Представим её в виде клетчатого поля $$$n \times m$$$. Перед началом игры, ни одна клетка этого поля ещё не построена. Игроки ходят по-очереди. За ход игрок может выбрать на поле любой прямоугольник с площадью не превышающей $$$s$$$, ни одна клетка которого ещё не построена, и построить все клетки внутри выбранного прямоугольника. Проигрывает игрок, который не может сделать ход. Сэм ходит первым. Помогите ему определить, выиграет ли он, при условии, что оба игрока стремятся выиграть и играют оптимально.

Аврора и Нотграсс решили сыграть в теннис и попросили Флитл побыть судьёй. Изначально их счет равнялся $$$0 : 0$$$. Затем, несколько раз очки одного из игроков увеличивались на $$$1$$$. А закончилась игра со счётом $$$a : b$$$.

Фислвит было скучно, поэтому она считала сумму НОД-ов очков игроков после каждого изменения счёта. НОД — наибольший общий делитель двух чисел. Например, игра могла проходить так:

• $$$0 : 0$$$
• $$$1 : 0$$$, $$$\textrm{НОД}(1, 0) = 1$$$
• $$$2 : 0$$$, $$$\textrm{НОД}(2, 0) = 2$$$
• $$$2 : 1$$$, $$$\textrm{НОД}(2, 1) = 1$$$
• $$$2 : 2$$$, $$$\textrm{НОД}(2, 2) = 2$$$
• $$$2 : 3$$$, $$$\textrm{НОД}(2, 3) = 1$$$

В таком случае, у Фислвит получилась бы сумма $$$1 + 2 + 1 + 2 + 1 = 7$$$.

После игры Фислвит стало интересно, какое наименьшее число могло у неё получиться. Помогите ей найти это значение.

Сегодня у Филиппа и Авроры свадьба, на которую приглашены все феи Топких Болот. Аврора слегка заскучала и решила понаблюдать за общением фей.

Исходно на свадьбе находится $$$n$$$ фей, Аврора пронумеровала их от $$$1$$$ до $$$n$$$. Фея номер $$$i$$$ характеризуется своей общительностью — целым неотрицательным числом $$$a_i$$$.

За время наблюдения, Аврора видела $$$q$$$ интересных моментов. Во время $$$j$$$-го из них происходило событие одного из трех типов:

1. На свадьбу приходит фея с общительностью $$$v_j$$$. Аврора назначает ей первый неиспользованный ранее номер. Например, первая пришедшая фея получит номер $$$n + 1$$$, следующая — $$$n + 2$$$ и так далее.
2. Фея с номером $$$p_j$$$ покидает свадьбу.
3. На свадьбе объявляется танец, характеризующийся своей экспрессивностью $$$e_j$$$ — целым неотрицательным числом. После танца, общительности всех фей изменяются. Если до танца фея имела общительность $$$b$$$, то после ее общительность станет равна $$$b \oplus e_j$$$, то есть побитовому исключающему ИЛИ чисел $$$b$$$ и $$$e_j$$$.

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

«Клуб неудачников» под предводительством Билла пытается сбежать из заброшенного дома, в котором на них напал Пеннивайз. Дом можно представить в виде таблицы размера $$$n \times m$$$, каждая клетка которой либо свободна, либо занята стенкой. Изначально, компания друзей находится в некоторой свободной клетке, а выход из дома находится в другой свободной клетке. Друзья могут переходить между соседними по стороне свободными клетками.

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

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

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

Всего в бою будет участвовать $$$n$$$ друзей. Для эффективности ведения боя пронумеруем их от $$$1$$$ до $$$n$$$. Исходно друзья выстроились в ряд, причем на $$$i$$$-е место в ряду встал друг с номером $$$a_i$$$. После долгих размышлений, Майк пришел к выводу, что наиболее эффективное расположение друзей будет достигнуто, если на $$$i$$$-м месте в ряду будет стоять друг с номером $$$b_i$$$.

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

Например, если друзья стояли в порядке $$$3, 4, 7, 6, 2, 5, 1$$$, а Майк выбрал друзей с номерами $$$4, 7, 5$$$, после перестроения друзья будут стоять в порядке $$$5, 7, 4, 3, 6, 2, 1$$$.

Бой с Пеннивайзом начнется довольно скоро, поэтому Майк хочет расположить друзей в желаемом порядке не более, чем за $$$15$$$ перестроений. Помогите ему справиться с этой задачей!

Обратите внимание, что минимизировать количество перестроений не требуется. Гарантируется, что, за не более чем $$$15$$$ перестроений, добиться желаемого порядка возможно.

Развлекаясь с ранее неизведанными заклинаниями, Малефисента случайно получила свиток с посланием из будущего. На свитке было написано какое-то занимательное заклинание.

<note>
<to></to>
<from></from>
<heading></heading>
<body></body>
</note>

Малефисента сразу заметила несколько закономерностей. А именно: заклинание представляет из себя правильную скобочную последовательность, в которой открывающаяся скобка соответствует шаблону «<S>», а парная ей закрывающаяся — шаблону «</S>», где строка S — непустая строка из строчных латинских букв, равная для парных скобок.

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