После долгого дня Алиса и Боб решили сыграть в игру. Игровая доска состоит из \(n\) ячеек на прямой, пронумерованных от \(1\) до \(n\), где каждая ячейка содержит число \(a_i\) в диапазоне от \(1\) до \(n\). Кроме того, никакие две ячейки не содержат одинаковые числа.

Игровая фигурка находится на одной ячейке. Они ходят по очереди, двигая фигурку. Алиса ходит первая. Игрок, который ходит, может передвинуть фигурку с ячейки \(i\) на ячейку \(j\), только если выполняются условия:

• число в новой ячейке \(j\) строго больше, чем в старой ячейке \(i\) (то есть \(a_j > a_i\)), и
• расстояние, на которое передвигается фигурка в этом ходу, должно делиться на число, расположенное в старой ячейке (то есть \(|i-j|\bmod a_i = 0\)).

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

Алиса и Боб играют в игру со строками.

Изначально у них есть какая-то строка \(t\). За один ход первый игрок выбирает какой-то символ \(c\), присутствующий в строке \(t\), и удаляет все его вхождения в \(t\), тем самым разбивая \(t\) на много меньших строк. Игра затем продолжается на этих строках независимо: чтобы сделать ход, игрок должен выбрать одну из строк и один символ из неё, удалить все его вхождения, и вернуть получившиеся строки назад в игру.

Алиса начинает игру, после чего Алиса и Боб ходят по очереди. Игрок, который не может сделать ход (потому что не осталось ни одной строки), проигрывает.

Алиса и Боб привыкли играть со строкой \(s\), но недавно им стало это надоедать. Теперь перед каждой игрой они выбирают два целых числа \(l\) и \(r\) такие, что \(1 \le l \le r \le |s|\) и играют вместо этого на строке \(s_{l} s_{l+1} s_{l+2} \ldots s_{r}\).

Вам дана строка \(s\) и целые числа \(l\) и \(r\) для каждой игры. Выясните, кто выиграет каждую игру, если оба игрока умные и играют оптимально.

Алиса и Боб играют в игру на поле с \(n\) строками и бесконечным количеством столбцов. В каждой строке есть три фишки: синяя, белая и красная. Перед началом игры и после каждого хода должны выполнятся следующие два условия:

• Любые две фишки находятся в разных ячейках.
• В каждой строке синяя фишка находится слева от белой, а красная фишка справа от белой.

Сначала Алиса и Боб выбирают целое положительное число \(f\), значение которого не меняется на протяжении игры. Потом начинающий игрок делает его/её первый ход, после которого игроки ходят по очереди. Игрок, который не может сделать ход, проигрывает.

Когда игрок делает ход, он выбирает целое число \(k\), которое либо простое число, либо произведение двух (не обязательно различных) простых чисел. Наименьшие возможные значения \(k\): \(2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 19, \dots\). Более того, \(k\) не должно быть равно тому \(f\), которое было выбрано в начале игры. Каждый ход происходит только в одной строке.

Если это ход Алисы, то она выбирает синюю фишку и передвигает её на \(k\) ячеек вправо. Или же она может передвинуть и синюю, и белую фишки в одной и той же строке на \(k\) ячеек вправо.

Боб, в свою очередь, выбирает красную фишку и передвигает её на \(k\) ячеек влево. Альтернативно, он может передвинуть и белую, и красную фишки в одной и той же строке на \(k\) ячеек влево.

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

Оба игрока играют оптимально. Учитывая начальное состояние игрового поля, определите, кто победит в двух играх: если Алиса начинает игру, и если начинает Боб.

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

Даша и NN — заядлые шахматисты. Во время очередной партии они поняли, что обычные шахматы им уже неинтересны, поэтому они придумали следующую игру.

На шахматной доске размером \(999 \times 999\) расположено \(666\) чёрных ладей и \(1\) белый король. Задача белого короля — попасть под шах ладьи, т. е. встать на такое поле, что на одной горизонтали или вертикали с ним будет находиться чёрная ладья.

Ходы совершаются по очереди, начинают белые. NN играет за белого короля, на каждом ходу он перемещает короля в одну из соседних по стороне или диагонали клеток, т. е. если король стоит на поле \((x, y)\), то он может переместиться на поле \((nx, ny)\) такое, что \(\max (|nx - x|, |ny - y|) = 1\) , \(1 \leq nx, ny \leq 999\). При этом NN не имеет права брать фигуры Даши, т. е. перемещаться на поле, на котором в данный момент находится чёрная ладья. Однако он может вставать на одну горизонталь или вертикаль с черными ладьями.

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

Каждый игрок делает \(2000\) ходов, если за это время белый король не попадет под шах ладьи, то победителем объявляются чёрные.

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

Чтобы сделать ход королем, выведите два целых числа \(x\) и \(y\) (\(1 \leq x, y \leq 999\)) — поле, на которое будет перемещен король. Король не имеет права вставать на поле, на котором в данный момент находится черная ладья (т. е. король не может брать ладьи). Гарантируется, что у короля в каждый момент будет возможность совершить корректный ход.

После каждого вашего хода считайте ход ладьи в следующем формате: в одной строке находятся три целых числа \(k\), \(x\) и \(y\) (\(1 \leq k \leq 666\), \(1 \leq x_i, y_i \leq 999\)) — номер ладьи, совершающей ход и поле, на которое ладья перемещается. Гарантируется, что ладья не будет перемещаться на поле, в котором в данный момент стоит другая ладья или король, но при этом ладья может совершить ход на поле, в котором она находилась до хода (т. е. остаться на том же поле). Гарантируется, что после хода ладьи король не будет под шахом. В случае, если ваш король попал под шах ладьи, все три числа будут равны \(-1\), после чего ваша программа должна немедленно завершиться.

После вывода хода не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

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

Взломы в этой задаче запрещены.

Игра в крестики-нолики начинается на дереве из \(n\) вершин. Некоторые вершины уже окрашены в белый цвет, а остальные пока бесцветны.

Есть два игрока — белый и чёрный. Игроки ходят по очереди, белый игрок начинает игру. В свой ход игрок выбирает ещё не покрашенную вершину и красит её в свой цвет.

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

Не могли бы вы выяснить, кто выиграет эту игру или закончится ли она в ничью, если оба игрока играют оптимально?

Вам дан полный двудольный граф с \(2n\) вершинами, с \(n\) вершинами в каждой доле. Вершины от \(1\) до \(n\) находятся в одной доле, а вершины от \(n+1\) до \(2n\) — в другой. Вам также дается \(n \times n\) матрица \(a\), описывающая веса ребер. \(a_{ij}\) обозначает вес ребра между вершинами \(i\) и \(j+n\). Каждое ребро имеет определенный вес.

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

Текущий игрок должен переместить фишку из текущей вершины в некоторую соседнюю не посещенную вершину. Пусть \(w\) будет вес последнего пройденного ребра. Вес следующего ребра должен быть строго больше, чем \(w\), если игрок играет за «увеличение», в противном случае он должен быть строго меньше. Первый игрок, который не может сделать ход, проигрывает.

Вам даны \(n\) и веса ребер графа. Вы можете играть за Алису или Боба, и вы будете играть против тестирующей программы. Вы должны выиграть все игры.

Во входных данных находятся несколько (не меньше одного) тестовых случаев. В первой строке находится одно целое число \(t\) (\(1 \le t \le 50\)) — количество тестовых случаев. Далее следуют описания тестовых случаев.

Первая строка описания тестового случая содержит одно целое число \(n\) (\(1 \leq n \leq 50\)) — количество вершин в каждой доле.

Каждая из следующих \(n\) строк содержит \(n\) целых чисел \(a_{ij}\) (\(1 \leq a_{ij} \leq n^2\)). \(a_{ij}\) обозначает вес ребра между вершиной \(i\) и вершиной \(j+n\). Гарантируется, что все \(a_{ij}\) различны.

Сначала выведите «A» или «B», этот символ обозначает за какого игрока вы хотите играть («A» за Алису и «B» за Боба).

Если вы играете за Алису, выведите либо «I», либо «D» (обозначает способ игры «увеличение» («I») или «уменьшение» («D»). После этого выведите вершину, в которой вы хотите начать игру.

Если вы играете за Боба, считайте символ «I» или «D» (обозначает способ игры, который выбрала тестирующая программа), после этого считайте вершину, которую тестирующая программа выбрала для начала.

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

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

Если вы считали \(-2\), это значит, что у вас неправильный запрос, и вам нужно немедленно прекратить вашу программу, чтобы избежать других вердиктов.

Если вы не можете походить или сдались, выведите \(-1\) и немедленно прекратите вашу программу. В таком случае вы получите вердикт Неправильный ответ.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Формат для взломов

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

Первая строка должна содержать одно целое число \(t\) (\(t=1\)).

Вторая строка должна содержать одно целое число \(n\) (\(1 \leq n \leq 50\)).

Каждая из следующих \(n\) строк должна содержать \(n\) целых чисел \(a_{ij}\) (\(1 \leq a_{ij} \leq n^2\)). \(a_{ij}\) обозначает вес ребра между вершиной \(i\) и вершиной \(j+n\). Все \(a_{ij}\) должны быть различны.

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

Телефонный номер — это последовательность из ровно \(11\) цифр, в которой первая цифра это 8.

Вася и Петя играют в игру. Изначально у них есть строка \(s\) длины \(n\) (\(n\) нечетно), состоящая из десятичных цифр. Игроки ходят по очереди, первым ходит Вася. Во время своего хода игрок должен удалить символ из строки по своему выбору. Например, строка 1121 после хода игрока может превратиться в строки 112, 111 или 121. Игра заканчивается, когда длина строки \(s\) становится равной 11. Если получившаяся строка является телефонным номером, то выиграл Вася, иначе — Петя.

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

"Duel!"

Только что началась дуэль между Tokitsukaze и Quality за прекрасную принцессу Claris.

Есть \(n\) карт, расположенных в ряд. Каждая карта имеет две стороны, одна из которых покрашена в некоторый цвет. В начале дуэли некоторые из карт лежат одной цветной стороной вверх, а некоторые — цветной стороной вниз. Игроки ходят, переворачивая карты, при этом Tokitsukaze ходит первым. Каждый ход игрок выбирает ровно \(k\) последовательных карт и переворачивает их так, чтобы или все они лежали цветной стороной вниз, или все они лежали цветной стороной вверх. Если все цветные стороны этих \(n\) карт смотрят в одном направлении после хода игрока, он выигрывает.

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

Алиса и Боб собираются сыграть в игру. У них есть \(n\) раскрашенных полосок бумаги; \(i\)-я полоска поделена на \(a_i\) клеток, пронумерованных от \(1\) до \(a_i\). Каждая клетка может быть раскрашена в один из \(3\) цветов.

В самом начале игры Алиса и Боб ставят на полоски \(n\) фишек, \(i\)-я фишка ставится в клетку \(a_i\) полоски \(i\). Затем игроки совершают ходы по очереди, Алиса ходит первой. В процессе хода игрок должен выбрать ровно одну фишку и подвинуть ее на \(1\), \(2\) или \(3\) клетки к началу полоски (если текущая клетка имеет номер \(x\), то можно подвинуть фишку в клетку \(x - 1\), \(x - 2\) или \(x - 3\)). Есть два ограничения: фишка не может покидать пределы полоски (например, если фишка находится в ячейке \(3\), нельзя подвинуть ее на \(3\) ячейки); и некоторые ходы могут быть недоступны из-за цвета текущей клетки (эти запреты обозначаются матрицей \(f\) размера \(3 \times 3\), где \(f_{i, j} = 1\), если можно подвинуть фишку на \(j\) клеток к началу полоски из клетки с цветом \(i\), или \(f_{i, j} = 0\), если этот ход недоступен). Игрок, который не может сделать ход, проигрывает.

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

Боб хочет посчитать количество хороших раскрасок. Можете ли вы сделать это для него?

Так как ответ может быть очень большим, выведите его по модулю \(998244353\).

Монокарп и Бикарп живут в Берляндии, где все автобусные билеты состоят из \(n\) цифр, при этом \(n\) — четное число. Гуляя вечером, они нашли билет, некоторые цифры на котором были стерты. Количество позиций, в которых цифры стерты, четно.

Монокарп и Бикарп решили сыграть в игру, используя найденный билет. Монокарп очень не любит счастливые билеты, в то время как Бикарп коллекционирует счастливые билеты. Билет считается счастливым, если сумма первых \(\frac{n}{2}\) цифр билета равна сумме последних \(\frac{n}{2}\) цифр билета.

Монокарп и Бикарп будут ходить по очереди, первый ход сделает Монокарп. На каждом своем ходу игроки будут записывать на место какой-то стертой цифры произвольную цифру от \(0\) до \(9\). Игра заканчивается, когда в билете не останется позиций со стертыми цифрами.

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

Алиса и Боб играют в игру. Изначально у них есть строка \(s_1, s_2, \dots, s_n\), состоящая только из символов . и X. Игроки ходят по очереди, и Алиса ходит первой. В течении хода игрок должен выбрать непрерывную подстроку, состоящую только из символов ., и заменить каждый символ в ней на X. Алиса выбирает подстроки длины ровно \(a\), а Боб выбирает подстроки длины ровно \(b\). Гарантируется, что \(a > b\).

Например, если \(s =\) ...X.. и \(a = 3\), \(b = 2\), то после хода Алисы строка может превратиться только в XXXX... Если \(s =\) ...X.., и сейчас ход Боба, то после него строка может превратиться в XX.X.., .XXX.. или ...XXX.

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

Вам нужно ответить на \(q\) независимых запросов.

Красное Королевство атаковано войсками Белого Короля и Черного Короля!

Королевство охраняют \(n\) замков, \(i\)-й из которых защищают \(a_i\) солдат. Чтобы захватить Королевство, необходимо уничтожить всех солдат, защищающих замки.

Каждый день Белый Король атакует один из замков. Затем ночью войска Черного Короля атакуют один из замков (возможно, тот же самый). После этого снова следует атака Белого Короля, потом атака Черного Короля, и так далее. Первую атаку проводит Белый Король.

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

• смешанная атака уменьшает количество защитников замка на \(x\) (или до \(0\), если их было меньше \(x\));
• атака пехоты уменьшает количество защитников замка на \(y\) (или до \(0\), если их было меньше \(y\));
• атака конницы уменьшает количество защитников замка на \(z\) (или до \(0\), если их было меньше \(z\)).

Смешанная атака может быть проведена по любой цели (по любому замку, в котором жив хотя бы один защитник). Однако атака пехоты не может быть проведена по замку, если предыдущая атака на этот замок была того же самого типа, вне зависимости от того, кто и когда провел эту атаку. То же самое относится к атаке конницы. Еще не атакованный замок доступен как цель для атаки любого типа.

Король, который проведет последнюю атаку, будет прославлен как завоеватель Красного Королевства, поэтому оба Короля хотят провести последнюю атаку (и они достаточно мудры, чтобы составить план действий, который позволит им это сделать вне зависимости от действий оппонента, если это возможно). Войска Белого Короля готовятся к первой атаке, а вам поручено ее распланировать. Сможете ли вы посчитать количество возможных вариантов первой атаки, при которых у Белого Короля есть стратегия, позволяющая ему провести последнюю атаку вне зависимости от действий Черного Короля? Каждый вариант первой атаки — это тип атаки и номер атакуемого замка, и два варианта различны, если хоть что-то из этого отличается в этих вариантах.

Алиса и Боб играют в игру (да, опять).

У них есть две последовательности отрезков на числовой прямой: последовательность из \(n\) начальных отрезков: \([l_1, r_1]\), \([l_2, r_2]\), ..., \([l_n, r_n]\), и последовательность из \(m\) конечных отрезков: \([L_1, R_1]\), \([L_2, R_2]\), ..., \([L_m, R_m]\). В начале игры они выбирают один из начальных отрезков в качестве текущего отрезка.

Алиса и Боб ходят по очереди: Алиса делает первый ход, затем ходит Боб, после него Алиса и т. д. Во время своего хода игрок обязан уменьшить текущий отрезок либо увеличением его левой границы на \(1\), либо уменьшением его правой границы на \(1\). Таким образом, если текущий отрезок \([c_l, c_r]\), то он превратится либо в \([c_l + 1, c_r]\), либо в \([c_l, c_r - 1]\).

Если в начале игры либо после хода Боба текущий отрезок совпадает с одним из конечных отрезков — то Боб выигрывает. Если текущий отрезок стал вырожденным (\(c_l = c_r\)), и Боб еще не выиграл — то выигрывает Алиса. Если текущий отрезок совпадает с одним из конечных отрезков после хода Алисы — игра продолжается.

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

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

Ayush и Ashish играют в игру на некорневом дереве, состоящем из \(n\) вершин, пронумерованных от \(1\) до \(n\). Игроки делают следующий ход по очереди:

   
• Выберите любой лист в дереве и удалите его вместе со всеми ребрами, для которых этот лист является одним из концов. Лист  — это вершина со степенью, не превосходящей \(1\).

Дерево  — это связный неориентированный граф без циклов.

Дана специальная вершина с номером \(x\). Игрок, который удаляет эту вершину, выигрывает игру.

Ayush ходит первым. Определите победителя игры, если каждый игрок играет оптимально.

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

Джон и его воображаемый друг играют в игру. По кругу расположено \(n\) лампочек. Лампочки пронумерованы от \(1\) до \(n\) по часовой стрелке, то есть, лампочки \(i\) и \(i + 1\) являются соседними для любого \(i = 1, \ldots, n - 1\), а также соседними являются лампочки \(n\) и \(1\). Исходно все лампочки выключены.

Джон и его друг ходят по очереди, начиная с Джона. Джон в качестве своего действия может завершить игру либо сделать ход. Чтобы сделать ход, Джон выбирает положительное число \(k\) и может включить любые \(k\) лампочек на свой выбор. Его друг в ответ может выбрать любые \(k\) подряд идущих лампочек и выключить их (выбранные лампочки, которые уже были выключены, остаются выключенными), где \(k\) равно числу, которое выбрал Джон на последнем ходу. Например, если \(n = 5\) и Джон только что включил три лампочки, то его друг может выключить лампочки \(1, 2, 3\), или \(2, 3, 4\), или \(3, 4, 5\), или \(4, 5, 1\), или \(5, 1, 2\).

После этого Джон снова может завершить игру или сходить, и так далее. Однако, Джон не может сделать более \(10^4\) ходов.

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

Пусть в игре \(n\) лампочек. Обозначим \(R(n)\) количество включенных лампочек в конце игры, если оба игрока действуют оптимально. Ваша программа должна сделать не более \(10^4\) ходов и завершить игру не менее чем с \(R(n)\) включенными лампочками. Детали реализации приведены в секции «Протокол взаимодействия».

По техническим причинам взломы по этой задаче невозможны.

Исходно ваша программа получит на вход одно целое число \(n\) (\(1 \leq n \leq 1000\)) — количество лампочек в игре. После этого программа жюри будет ожидать ваших действий.

Чтобы сделать ход, выведите в одной строке целое число \(k\) (\(1 \leq k \leq n\)), а зачем \(k\) различных целых чисед \(l_1, \ldots, l_k\) (\(1 \leq l_i \leq n\)) — номера лампочек, которые вы хотите включить. Индексы можно выводить в любом порядке. Можно пытаться включать лампочки, которые уже включены (в таком случае их состояние не изменится).

Если ваш ход по какой-либо причине некорректен, или вы совершили более \(10^4\) ходов, программа жюри выведет одно число \(-1\). В противном случае, программа жюри выведет одно целое число \(x\) (\(1 \leq x \leq n)\). Это означает, что в ответ были выключены \(k\) лампочек, начиная с лампочки номер \(x\) в порядке по часовой стрелке.

Чтобы вместо следующего хода завершить игру, выведите в отдельной строке одно число \(0\). Тест будет пройден, если в этот момент включено не менее \(R(n)\) лампочек (значение \(R(n)\) и полученный вердикт не будут сообщены вашей программе). Это действие не включается в количество сделанных ходов (то есть, разрешается завершить игру после ровно \(10^4\) ходов).

Чтобы получить правильный вердикт, ваша программа должна завершиться сразу, как только выведет \(0\) либо получит ответ \(-1\).

Не забудьте сбросить буфер вывода после каждого действия.

Ashishgup и FastestFinger играют в игру.

Они начинают с целого числа \(n\) и начинают делать ходы по очереди. На каждом ходу игрок может сделать любой из следующих двух ходов:

• Разделить \(n\) на один из его нечетных делителей, который больше чем \(1\).
• Вычесть \(1\) из \(n\), если \(n\) больше чем \(1\).

Обратите внимание, что множество делителей числа включает само число.

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

Ashishgup ходит первым. Определите победителя игры, если оба игрока играют оптимально.

Алиса и Боб играют в игру.

Изначально у них есть строка \(s\), состоящая только из символов 0 и 1.

Алиса и Боб ходят по очереди: Алиса делает первый ход, второй делает Боб, третий ход делает Алиса, и так далее. Во время своего хода игрок должен выбрать два соседних различных символа строки \(s\) и удалить их. Например, если \(s = 1011001\), тогда возможны следующие ходы:

1. удалить \(s_1\) и \(s_2\): \(\textbf{10}11001 \rightarrow 11001\);
2. удалить \(s_2\) и \(s_3\): \(1\textbf{01}1001 \rightarrow 11001\);
3. удалить \(s_4\) и \(s_5\): \(101\textbf{10}01 \rightarrow 10101\);
4. удалить \(s_6\) и \(s_7\): \(10110\textbf{01} \rightarrow 10110\).

Если игрок не может сделать ход — он проигрывает. Оба игрока играют оптимально. Вам нужно определить, сможет ли Алиса выиграть.

Недавно Рома стал счастливым обладателем новой игры World of Darkraft. Эта игра сочетает элементы практически всех известных жанров, и на одном из поздних этапов игры Рома столкнулся с трудностями игры-головоломки.

В этой части Рома сражается с хитрым вражеским магом. Сражение происходит на прямоугольном клетчатом поле n × m. В каждой клетке находится один из магических символов: L, R или X. Изначально все клетки поля «активны».

Игроки, Рома и вражеский маг, ходят по очереди. Рома делает первый ход. На очередном ходу игрок выбирает одну из активных клеток, и после этого в зависимости от изображенного в ней символа происходит одно из следующих действий:

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

Если очередной игрок не может сделать ход (то есть все клетки неактивны), он проигрывает.

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

Коала Коа и ее лучшая подруга хотят поиграть в игру.

Игра начинается с массива \(a\) длины \(n\), состоящего из неотрицательных целых чисел. Коа и ее лучшая подруга ходят по очереди, и у каждой из них есть счет, изначально равный \(0\). Коа начинает.

Ход в игре происходит следующим образом:

• Во время своего хода игрок выбирает любой элемент массива и удаляет его из этого массива, ксоря его с текущим счетом игрока.

  Более формально: если текущий счет игрока равен \(x\), а выбранный элемент равен \(y\), его новый счет будет равен \(x \oplus y\). Здесь \(\oplus\) обозначает операцию побитового исключающего ИЛИ..

  Обратите внимание, что после хода элемент \(y\) удаляется из \(a\).

• Игра заканчивается, когда массив пуст.

В конце игры победителем становится игрок с максимальным счетом. Если оба игрока имеют одинаковый счет, то это ничья.

Если оба игрока играют оптимально, выясните, выиграет ли Коа, проиграет или сыграет вничью.

Алиса и Боб играют в игру. У них есть бинарная строка \(s\) (каждый символ бинарной строки — либо \(0\), либо \(1\)). Алиса ходит первой, потом Боб, потом снова Алиса, и так далее.

В свой ход игрок должен выбрать несколько (не менее одного) последовательных одинаковых символов в \(s\) и удалить их.

Например, если текущая строка — \(10110\), существует \(6\) возможных ходов (удаляемые символы выделены жирным):

1. \(\textbf{1}0110 \to 0110\);
2. \(1\textbf{0}110 \to 1110\);
3. \(10\textbf{1}10 \to 1010\);
4. \(101\textbf{1}0 \to 1010\);
5. \(10\textbf{11}0 \to 100\);
6. \(1011\textbf{0} \to 1011\).

После удаления символов те символы, которые стояли слева и справа от удаленного блока, становятся последовательными. Т. е. следующая последовательность операций возможна: \(10\textbf{11}0 \to 1\textbf{00} \to 1\).

Игра заканчивается, когда строка становится пустой. Счет каждого игрока равен кол-ву символов \(1\), которые он удалил.

Каждый игрок хочет набрать максимально возможное количество очков. Посчитайте, сколько очков наберет Алиса.

Алиса и Боб играют в забавную игру — догонялки на дереве.

В эту игру играют на дереве из \(n\) вершин, пронумерованных от \(1\) до \(n\). Напомним, что дерево на \(n\) вершинах — это неориентированный, связный граф с \(n-1\) ребрами.

Изначально Алиса располагается в вершине \(a\), а Боб — в вершине \(b\). Они ходят по очереди, и Алиса делает первый ход. За свой ход Алиса может перепрыгнуть в вершину с расстоянием не более \(da\) от текущей вершины. Боб же за свой ход может перепрыгнуть в вершину с расстоянием не более \(db\) от текущей вершины. Расстояние между двумя вершинами определяется как количество рёбер на уникальном простом пути между ними. В частности, любому из игроков разрешается остаться на одной и той же вершине в свой ход. Заметим, что при выполнении хода игрок занимает только начальную и конечную вершины своего хода, а не вершины между ними.

Если после не более чем \(10^{100}\) ходов Алиса и Боб занимают одну и ту же вершину, то победителем объявляется Алиса. В противном случае побеждает Боб.

Определите победителя, если оба игрока играют оптимально.

Ни для кого не секрет, что в Валоранте агенты разыгрывают стороны до начала матча, и делают это именно Рейз и Брич, которые решили, что для этого надо сыграть \(t\) партий следующей игры...

В каждой из \(t\) партий игры сначала генерируется какое-то положительное целое число, состоящее из \(n\) цифр. Цифры этого числа пронумерованы целыми числами от \(1\) до \(n\) от старшего разряда к младшему. После того, как число становится известно, начинается партия.

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

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

Для каждой из \(t\) партий определите, кто из агентов выиграет, если оба игрока хотят победить и действуют оптимально.

Lately, Mr. Chanek frequently plays the game Arena of Greed. As the name implies, the game's goal is to find the greediest of them all, who will then be crowned king of Compfestnesia.

The game is played by two people taking turns, where Mr. Chanek takes the first turn. Initially, there is a treasure chest containing \(N\) gold coins. The game ends if there are no more gold coins in the chest. In each turn, the players can make one of the following moves:

• Take one gold coin from the chest.
• Take half of the gold coins on the chest. This move is only available if the number of coins in the chest is even.

Both players will try to maximize the number of coins they have. Mr. Chanek asks your help to find the maximum number of coins he can get at the end of the game if both he and the opponent plays optimally.

Алиса и Боб играют в игру. У них есть множество, который изначально состоит из \(n\) целых чисел. Игра длится \(k\) ходов. Во время каждого хода происходит следующее:

1. сначала Алиса выбирает целое число из множества. Она может выбрать любое целое число кроме максимального. Пусть целое число, выбранное Алисой, равно \(a\);
2. затем Боб выбирает целое число из множества. Он может выбрать любое целое число которое больше \(a\). Пусть целое число, выбранное Бобом, равно \(b\);
3. наконец, и \(a\), и \(b\) удаляются из множества, а значение \(b - a\) добавляется к счету игры.

Изначально счет игры равен \(0\). Алиса хочет максимизировать итоговый счет, а Боб хочет минимизировать его. Предположив, что и Алиса, и Боб играют оптимально, вычислите итоговый счет игры.

Рассмотрим таблицу \((10^9+1) \times (10^9+1)\). Строки пронумерованы целыми числами от \(0\) до \(10^9\), и столбцы пронумерованы целыми числами от \(0\) до \(10^9\). Обозначим за \((x, y)\) клетку, расположенную в строке \(x\) в столбце \(y\).

Давайте назовем клетку \((x, y)\) хорошей, если \(x \& y = 0\), где \(\&\) — это операция побитового И.

Давайте построим граф, вершинами которого будут все хорошие клетки и проведем ребра между всеми парами соседних по стороне хороших клеток. Можно доказать, что этот граф является деревом — связным графом без циклов. Давайте подвесим это дерево за вершину \((0, 0)\), таким образом мы получим корневое дерево с корнем \((0, 0)\).

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

Изначально все клетки белые. Вам дано \(m\) пар клеток. Для каждой пары клеток все клетки на простом пути между клетками в паре красятся в черный цвет. Обратите внимание, что эти цвета не инвертируются, а мы красим клетки в черный цвет.

Sohrab и Mashtali собираются сыграть в эту игру. Sohrab будет первым игроком, а Mashtali вторым.

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

Mammad, который наблюдает за ними, задался вопросом: «какое минимальное количество операций должен сделать Mashtali, чтобы иметь выигрышную стратегию?».

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

Jeel и Ashish играют в игру на матрице \(n \times m\). Строки пронумерованы от \(1\) до \(n\) сверху вниз, а столбцы пронумерованы от \(1\) до \(m\) слева направо. Они ходят по очереди. Ashish ходит первым.

Исходно каждая клетка матрицы содержит неотрицательное целое число. На каждом ходу игрок должен выполнить все следующие операции по порядку.

• Выбрать стартовую клетку \((r_1, c_1)\) с ненулевым значением.
• Выбрать финишную клетку \((r_2, c_2)\) так, что \(r_1 \leq r_2\) и \(c_1 \leq c_2\).
• Уменьшить значение в стартовой клетке на положительное целое число.
• Выбрать любой кратчайший путь между двумя клетками и уменьшить/увеличить/не изменить все клетки на этом пути. Обратите внимание, что:
  • кратчайший путь это путь, который проходит по наименьшему числу клеток;
  • все клетки на этом пути не включают стартовую клетку, но финишная клетка может быть изменена;
  • итоговое значение каждой клетки должно быть неотрицательным целым числом;
  • клетки изменяются независимо, не обязательно на одно и то же число.

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

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

Для данной матрицы, если оба игрока играют оптимально, можете ли вы узнать, кто выиграет?

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

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

Чтобы упростить тестирование игры, вы добавили секреты, известные только разработчику. Есть \(n\) секретных позиций \((x_1, y_1), \ldots, (x_n, y_n)\), которые влияют на игру следующим образом. Пусть перед ходом одного из игроков первая и вторая кучка содержат \(x\) и \(y\) камней соответственно. Если пара чисел \((x, y)\) совпадает с одной из пар \((x_i, y_i)\), то игрок, который должен ходить следующим, немедленно проигрывает, в противном случае этот игрок ходит как обычно. Обратите внимание, что в описании выше кучки и все пары упорядочены, то есть, \(x\) обязательно означают размер первой кучки, а \(y\) обязательно означают размер второй кучки.

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

Дракон и принцесса решают, что делать в новогоднюю ночь: дракон предлагает лететь в горы любоваться танцами фей под луной, а принцесса — лечь спать пораньше. Договориться полюбовно они отчаялись и решили отдаться на волю случая.

Они по очереди тянут мышек из мешка, в котором изначально w белых и b черных мышек, и выигрывает тот, кто первым достает белую мышь. После каждой вытянутой драконом мыши оставшиеся впадают в панику, и одна из них выпрыгивает из мешка сама (принцесса вытаскивает мышей из мешка аккуратно и не пугает их). Принцесса тянет первой. Какова вероятность ее победы?

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

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

На листочке записана перестановка \(p\). Сначала Циншань выбирает индекс \(x\) (\(1\le x\le n\)) и сообщает его Даниэлю. После этого Даниэль выбирает другой индекс \(y\) (\(1\le y\le n\), \(y \ne x\)).

Далее начинается игра, в которой они ходят по-очереди, Циншань ходит первой. Правила следующие:

• В свой ход Циншань должна изменить значение \(x\) на \(x'\) так, что одновременно выполняются условия \(1\le x'\le n\), \(|x'-x|=1\), \(x'\ne y\) и \(p_{x'}<p_x\).
• В свой ход Даниэль должен изменить значение \(y\) на \(y'\) так, что одновременно выполняются условия \(1\le y'\le n\), \(|y'-y|=1\), \(y'\ne x\) и \(p_{y'}>p_y\).

Игрок, который не может сделать ход, проигрывает, а другой игрок выигрывает. Вы болеете за Циншань и должны определить, сколько существует различных способов выбрать в начале \(x\) так, чтобы Циншань выигрывала при условии, что оба игрока играют оптимально.

В городе Петрограде есть n камнедобывающих предприятий.

В каждом из них стоит в ряд m_i самосвалов (1 ≤ i ≤ n). Известно, что в первом самосвале i-го предприятия лежит x_i камней. Во втором самосвале x_i + 1 камень, в третьем x_i + 2, в m_i-ом (последнем для i-го предприятия) x_i + m_i - 1 камней.

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

Олигархи пожелали остаться неизвестными, но так как вам придется предугадывать, кто из них станет победителем при правильной игре, то если выиграет олигарх, который ходит первым, выведите «tolik», иначе «bolik».

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

Алиса и Боб играют в игру. Есть доска \(n\times n\), изначально пустая. Мы будем обозначать ячейку в строке \(i\) и столбце \(j\) как \((i, j)\) для \(1\le i, j\le n\). Также, есть бесконечный запас фишек \(3\) цветов, обозначенных \(1\), \(2\) и \(3\).

Алиса и Боб ходят по очереди по следующим правилам: каждый ход начинается с того, что Алиса называет один из трех цветов, назовем его \(a\). Затем Боб выбирает цвет \(b\ne a\), выбирает пустую ячейку и помещает на нее фишку цвета \(b\).

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

Если в какой-то момент возникает конфликт, Алиса побеждает. В противном случае, если было совершено \(n^2\) ходов (так что доска полностью заполнилась) без конфликтов, побеждает Боб.

У нас есть доказательство того, что у Боба есть выигрышная стратегия. Сыграйте в игру за Боба и выиграйте.

Интерактор адаптивен. Таким образом, выбор цвета Алисой может зависеть от предыдущих ходов Боба.

Взаимодействие начинается с чтения единственного целого числа \(n\) (\(2\le n\le 100\)) — размера доски.

Дальше начинаются ходы. Каждый ход следует начинать с чтения целого \(a\) (\(1\le a\le 3\)) — выбранного цвета Алисы.

Затем необходимо вывести три целых числа \(b,i,j\) (\(1\le b\le 3,b\ne a, 1\le i,j\le n\)) —, что означает, что Боб кладет в ячейку \((i, j)\) фишку цвета \(b\). Ячейка \((i, j)\) не должна содержать фишки из предыдущих ходов. Если ваш ход недействителен или проигрывает партию, взаимодействие прекратится и вы получите вердикт Неправильный ответ.

После того как все \(n^2\) ходов были сделаны, завершите программу, чтобы избежать неожиданных вердиктов.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Формат взломов

Для взлома используйте следующий формат.

Первая строка содержит одно целое число \(n\) (\(2\le n\le 100\)).

Вторая строка содержит \(n^2\) целых чисел \(a_1,\ldots,a_{n^2}\) (\(1\le a_i\le 3\)), где \(a_i\) обозначает цвет Алисы на \(i\)-м ходу игры.

Интерактор может отклониться от заданного во взломе порядка цветов, но только в том случае, если это заставит Боба проиграть.

Единственное отличие между простой и сложной версией заключается в том, что \(s\) в простой версии изначально является палиндромом, что не всегда верно в сложной версии.

Палиндромом называется строка, читающаяся одинаково слева направо и справа налево. Например, «101101» — палиндром, а «0101» — нет.

Алиса и Боб играют в игру со строкой \(s\) (которая изначально является палиндромом в простой версии) длины \(n\), состоящей из символов '0' и '1'. Оба игрока ходят по очереди, и Алиса делает первый ход.

За один ход игрок может сделать одну из следующих операций:

1. Выбрать любое \(i\) (\(1 \le i \le n\)) такое, что \(s[i] =\) '0', заменить \(s[i]\) на '1' и заплатить 1 доллар, или
2. Развернуть всю строку, заплатив 0 долларов. Эта операция доступна только в том случае, если сейчас строка не палиндром, и последняя операция была не разворотом. Это значит, что если Алиса развернула строку, то Боб не может развернуть ее следующим ходом, и наоборот.

Под разворотом строки подразумевается переупорядочивание символов от последнего к первому. Например, «01001» после разворота становится «10010».

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

Омкар и Акмар играют в игру на круговой доске с \(n\) (\(2 \leq n \leq 10^6\)) клетками. Клетки пронумерованы от \(1\) до \(n\), для каждой \(i\) (\(1 \leq i \leq n-1\)) клетка \(i\) соседствует с клеткой \(i+1\), а клетка \(1\) соседствует с клеткой \(n\). Изначально каждая клетка пуста.

Омкар и Акмар по очереди выкладывают на доску букву A или B, причем Акмар ходит первым. Буква должна быть помещена на пустую клетку. Кроме того, буква не может быть помещена в такую клетку, что соседняя клетка содержит ту же букву.

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

Выведите количество возможных различных игр, в которых оба игрока играют оптимально по модулю \(10^9+7\). Обратите внимание, что мы рассматриваем только те партии, в которых кто-то из игроков проиграл, и не осталось ни одного допустимого хода.

Две игры считаются разными, если количества ходов в них отличаются, или на каком-то ходу буква или номер клетки, на которую ставится буква, были разными.

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

Король Флатландии проводит рыцарский турнир! Победителю достанется полцарства и расположение принцессы, о красоте и мудрости которой ходят легенды. Последней проверкой смелости и силы претендентов будет турнир по фехтованию. Турнир проходит по следующим правилам: участники сражаются один на один, победитель (а точнее, выживший) выходит в следующий круг соревнований.

Перед битвой оба участника становятся в указанные им точки оси Ox с целыми координатами. Затем они совершают ходы по очереди. Первым, естественно, ходит первый участник. На своем ходу первый участник из точки x может переместиться в любую целочисленную точку из отрезка [x + a; x + b], а второй — в любую целочисленную точку из отрезка [x - b; x - a], то есть варианты ходов для игроков симметричны (обратите внимание, что числа a и b не обязаны быть положительными; также, если a ≤ 0 ≤ b, то остаться на месте — корректный ход.) В любой момент участники могут располагаться произвольным образом друг относительно друга, то есть «перепрыгивать» через противника в любую сторону позволяется. Побеждает тот участник, который на своем ходу переместится в точку, где находится его противник.

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

Алиса и Боб — два браконьера, которые рубят лес.

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

В этой задаче мы определим глубину вершины как количество вершин на простом пути от этой вершины до корня. Рангом дерева назовем минимальную глубину его листа.

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

Игрок проигрывает, если на момент начала его хода лес пуст.

Определите, может ли Алиса победить, если оба игрока играют оптимально.

Eikooc и Sushi играют в игру.

Игра проводится на дереве из \(n\) вершин, пронумерованных от \(1\) до \(n\). Напомним, что дерево с \(n\) вершинами это неориентированный связный граф с \(n-1\) ребрами.

Игроки поочередно перемещают фишку по дереву. Eikooc делает первый ход, помещая фишку на любую вершину по своему выбору. Sushi делает следующий ход, затем Eikooc, затем Sushi, и так далее. В каждый ход после первого, игрок должен переместить фишку в какую-то вершину \(u\) такую, что:

• Между вершинами \(u\) и \(v\) (на которой фишка находится данный момент), есть ребро
• \(u\) не была посещена ранее
• \(u \oplus v \leq min(u, v)\)

Здесь \(x \oplus y\) обозначает операцию побитового исключающего ИЛИ чисел \(x\) и \(y\).

Оба игрока играют оптимально. Игрок, который не может сделать ход, проигрывает.

Ниже приведены примеры, демонстрирующие правила игры.

Предположим, Eikooc начинает игру, помещая фишку в вершину \(4\). Затем Sushi перемещает фишку в вершину \(6\), которая не была посещена и является соседней к \(4\). Также \(6 \oplus 4 = 2 \leq min(6, 4)\). На следующем ходу Eikooc перемещает фишку в вершину \(5\), которая не была посещена и является соседней к \(6\). Также, \(5 \oplus 6 = 3 \leq min(5, 6)\). У Sushi больше нет ходов для игры, поэтому она проигрывает.

Предположим, Eikooc начинает игру, помещая фишку в вершинул \(3\). Sushi перемещает фишку в вершину \(2\), которая не была посещена и является соседней к \(3\). Также \(3 \oplus 2 = 1 \leq min(3, 2)\). Eikooc не может переместить фишку в вершину \(6\), так как \(6 \oplus 2 = 4 \nleq min(6, 2)\). Поскольку у Eikooc нет ходов для игры, она проигрывает.

Перед началом игры Eikooc решает тайком перенумеровать вершины дерева в свою пользу. Формально, перенумерация — это перестановка \(p\) длины \(n\) (последовательность из \(n\) целых чисел, где каждое целое число от \(1\) до \(n\) встречается ровно один раз), где \(p_i\) обозначает новый номер вершины \(i\).

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

Два игрока, Красный и Синий, снова в деле, и этот раз они играют с цветными мелками! Сегодня озорной паре под руку попалось корневое дерево, с которым они играют в свою любимую игру, раскрашивая вершины этого дерева.

Игра выглядит следующим образом: есть дерево из \(n\) вершин с корнем в вершине \(1\), и каждая вершина первоначально белого цвета. У Красного и Синего есть ровно по одному ходу. Первым ходит Красный.

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

• Он выбирает любое поддерево корневого дерева и красит каждую из вершин поддерева в красный.

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

• Он выбирает любое поддерево корневого дерева и красит каждую вершину поддерева в синий. Однако, ему нельзя выбирать поддеревья, в которых содержатся вершины, уже покрашенные в красный. Ведь в таком случае вершина получится фиолетового цвета, а никто не любит фиолетовый мелок* (англ. purple crayon).

После того как каждый сделает свой ход, счет игры определяется следующим образом: пусть \(w\) — количество оставшихся белых вершин, \(r\) — количество красных вершин, а \(b\) — количество синих вершин. Счет игры будет равен \(w \cdot (r - b)\).

Красный хочет максимизировать счет, а Синий — минимизировать. Чему будет равен счет игры, если оба игрока действуют оптимально?

Рахул и Тина с нетерпением ждут начала нового учебного года в колледже. Вот они заходят в учебный класс и видят, что места для студентов расположены в виде прямоугольника \(n \times m\). Место, соответствующее клетке в строке \(r\) столбце \(c\) этого прямоугольника, обозначается как \((r, c)\). Расстояние между двумя местами \((a,b)\) и \((c,d)\) вычисляется по формуле \(|a-c| + |b-d|\).

Как президент класса, Тина имеет доступ к ровно \(k\) ведрам розовой краски. Далее происходит следующий процесс.

• Сначала Тина выбирает ровно \(k\) мест в классе, чтобы покрасить их розовой краской. Одним ведром краски можно покрасить ровно одно место.
• После того как Тина покрасит \(k\) мест в розовый цвет, Рахул выбирает, где ему сесть. Он не выберет место, покрашенное в розовый цвет, так как он очень не любит розовый.
• После того, как Рахул выберет свое место, Тина выбирает место для себя. Она может выбрать любое место, покрашенное или нет, за исключением того места, которое выбрал Рахул.

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

Теперь Рахул задается вопросом: для \(k = 0, 1, \dots, n \cdot m - 1\), если у Тины есть \(k\) ведер с краской, насколько близко Рахул может сидеть к Тине, если и Рахул, и Тина знают о намерениях друг друга и оба действуют оптимально? Пожалуйста, помогите удовлетворить любопытство Рахула!

Это сложная версия задачи. Разница заключается в ограничениях на \(n\), \(m\) и \(t\). Делать взломы можно только в том случае, если решены обе задачи.

Алисе и Бобу даются числа \(n\), \(m\) и \(k\), и они играют в следующую игру:

В игре есть счет, который Алиса пытается максимизировать, а Боб старается минимизировать. Первоначально счет равен \(0\). Игра состоит из \(n\) ходов. Каждый ход Алиса выбирает число от \(0\) до \(k\) (необязательно целое), которое Боб либо прибавляет, либо вычитает из счета игры. Но на протяжении всей игры Боб должен прибавить не менее \(m\) из \(n\) ходов.

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

Если Алиса и Боб будут играть оптимально, каков будет окончательный счет игры?

Есть дерево из \(n\) вершин и перестановка \(p\) из \(n\) чисел. В вершине \(x\) дерева находится фишка.

Алиса и Боб играют в игру. Алиса управляет перестановкой \(p\), а Bob управляет фишкой на дереве. В свой ход Алиса обязана выбрать два различных числа \(u\) и \(v\) (не индексы; \(u \neq v\)) такие, что фишка не находится ни в вершине \(u\), ни в вершине \(v\) дерева, и поменять их местами в перестановке \(p\). В свой ход Боб обязан передвинуть фишку в соседнюю с текущей вершину.

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

По данному дереву, перестановке \(p\) и вершине \(x\), в которой изначально находится фишка, определите победителя игры.

В некоторой стране живут волшебники. Они любят играть с числами.

На доске записано два числа — a и b. Порядок чисел не важен. Пусть для определенности a ≤ b. Игроки по очереди могут колдовать одно из двух заклинаний.

• Заменить b на b - a^k. Число k может выбрать игрок, с ограничениями, что k > 0 и b - a^k ≥ 0. Число k выбирается независимо при каждом использовании заклинания игроком, делающим ход.
• Заменить b на b mod a.

В случае, когда a > b возможны аналогичные ходы.

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

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

Алиса и Боб играют в игру со строками. Всего в игре будет \(t\) раундов. В каждом раунде будет строка \(s\), состоящая из строчных латинских букв.

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

Более формально, если была строка \(s = s_1s_2 \ldots s_k\) игрок может выбрать подстроку \(s_ls_{l+1} \ldots s_{r-1}s_r\) длины соответствующей чётности и удалить её. После этого строка станет \(s = s_1 \ldots s_{l-1}s_{r+1} \ldots s_k\).

Когда строка становится пустой, раунд заканчиваются и каждый игрок считает его/её очки за этот раунд. Количество очков игрока равно сумме стоимостей символов, удалённых им/ей. Стоимость \(\texttt{a}\) равна \(1\), стоимость \(\texttt{b}\) равна \(2\), стоимость \(\texttt{c}\) равна \(3\), \(\ldots\), и стоимость \(\texttt{z}\) равна \(26\). Игрок с большим количеством очков побеждает в раунде. Для каждого раунда определите победителя и разницу очков победителя и проигравшего. Считайте, что оба игрока играют оптимально с целью максимизировать свои очки. Можно доказать, что ничья невозможна.

У самых истоков CrowdForces, ещё совсем давно, стояла именно Тётя Люсине. За это время она заработала много денег, даже забыла все цифры и теперь просто платит. Но совершенно неожиданно ей на ревью попалась задача как раз на цифры! Тётя Люсине не может решить даже on-ramp задачу. Помогите ей, ведь судьба вашего аккаунта в её руках!

Дано целое число \(n\) без нулей в десятичной записи. Алиса и Боб играют в игру с этим числом. Алиса начинает первой. Они делают ходы по очереди.

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

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

Майк и Джо играют в игру с камнями. У них есть \(n\) кучек камней размерами \(a_1, a_2, \ldots, a_n\). Эти кучки расположены по кругу.

Игра проходит следующим образом. Игроки по очереди удаляют некоторое положительное число камней из кучек по часовой стрелке, начиная с кучки \(1\). Формально, если игрок в свой ход убрал камни из кучки \(i\), то другой игрок в следующий ход убирает камни из кучки \(((i\bmod n) + 1)\).

Если игрок не может убрать ни одного камня в свой ход (потому что кучка пуста), он проигрывает. Майк ходит первым.

Если Майк и Джо играют оптимально, кто выиграет?

Вам даны два массива целых чисел \(a_1,a_2,\dots,a_n\) и \(b_1,b_2,\dots,b_m\).

Алиса и Боб играют в игру. Алиса ходит первой, а затем они ходят по очереди.

Они играют на доске \(n \times m\) (\(n\) строк и \(m\) столбцов). Изначально в клетке в первой строке и первом столбце стоит ладья.

В свой ход игрок может сделать одну из следующих двух операций:

1. Переместить ладью в другую клетку в том же ряду или в том же столбце с текущей клеткой. Игрок не может переместить ладью в клетку, которая уже была посещена \(1000\) раз до этого (т. е. ладья может находиться на одной клетке не более \(1000\) раз за всю игру). Обратите внимание, что стартовая клетка считается уже посещенной один раз в начале игры.
2. Немедленно закончить игру со счетом \(a_r+b_c\), где \((r, c)\) — координаты текущей клетки (т. е. ладья находится в \(r\)-й строку \(c\)-м столбце).

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

Алиса и Боб играют в игру. Изначально им дана непустая строка \(s\), состоящая из строчных латинских букв. Длина строки четная. У каждого игрока также есть своя строка, изначально пустая.

Алиса начинает, затем они ходят по очереди. За один ход игрок берет либо первую, либо последнюю букву из строки \(s\), удаляет ее из \(s\) и приписывает ее в начало своей строки.

Игра заканчивается, когда строка \(s\) становится пустой. Побеждает игрок, у которого строка лексикографически меньше. Если строки у игроков одинаковые, то это ничья.

Строка \(a\) лексикографически меньше строки \(b\), если существует такая позиция \(i\), что \(a_j = b_j\) для всех \(j < i\) и \(a_i < b_i\).

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

Алиса и Боб играют в игру на последовательности \(a_1, a_2, \dots, a_n\) длины \(n\). Их ходы чередуются, и Алиса ходит первой.

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

Алиса выигрывает, если сумма убранных ей чисел четная; в противном случае выигрывает Боб.

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

Есть \(n\) кубиков, пронумерованных от \(1\) до \(n\). Кубик \(i\) имеет вес \(a_i\).

У Пака Чанека есть \(3\) мешка с номерами от \(1\) до \(3\), которые изначально пусты. Каждый кубик Пак Чанек должен положить в один из мешков. После этого в каждом мешке должен оказаться хотя бы один кубик.

После того, как Пак Чанек разложит кубики, Бу Денгклек возьмет ровно по одному кубику из каждого мешка. Пусть \(w_j\) — вес кубика, который Бу Денгклек берет из мешка \(j\). Результатом всех действий назовем число \(|w_1 - w_2| + |w_2 - w_3|\), где \(|x|\) — модуль числа \(x\).

Известно, что Денгклек будет брать кубики таким образом, чтобы минимизировать результат. Чему равен максимально возможный результат, если Пак Чанек раскладывает кубики оптимально?

Алиса и Боб играют в игру. У них есть массив положительных целых чисел \(a\) размера \(n\).

Перед началом игры Алиса выбирает целое число \(k \ge 0\). Игра длится \(k\) ходов, номера ходов нумеруются от \(1\) до \(k\). На \(i\)-м ходу Алиса должна удалить из массива элемент, который меньше либо равен \(k - i + 1\). После этого, если массив не пустой, Боб должен прибавить к некоторому элементу массива \(k - i + 1\). Обратите внимание, что и действие Алисы, и следующее за ним действие Боба — это две части одного и того же хода. Если Алиса не может удалить элемент на каком-то ходу — она проигрывает. Если \(k\)-й ход закончился, а Алиса еще не проиграла, то она выигрывает.

Ваша задача — определить максимальное значение \(k\), при котором Алиса может выиграть при оптимальной игре обоих игроков. Боб играет против Алисы, поэтому он пытается, если это возможно, заставить ее проиграть.

Два игрока играют в игру. У них есть перестановка чисел \(1\), \(2\), ..., \(n\) (перестановка — это массив, в котором каждый элемент от \(1\) до \(n\) встречается ровно один раз). Перестановка не отсортирована ни в прямом, ни в обратном порядке (т.е. перестановка не имеет вид \([1, 2, \dots, n]\) или \([n, n-1, \dots, 1]\)).

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

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

Первый игрок выигрывает, если перестановка окажется отсортирована в порядке возрастания (т.е. станет равна \([1, 2, \dots, n]\)). Второй — если перестановка окажется отсортирована в порядке убывания (т.е. станет равна \([n, n-1, \dots, 1]\)). Если игра длится \(100^{500}\) ходов и никто не выигрывает, она заканчивается вничью.

Ваша задача — определить результат игры при оптимальной игре обоих игроков.

The two siblings Alberto and Beatrice have to eat a spinach pizza together. However, none of them likes spinach, so they both want to eat as little as possible.

The pizza has the shape of a strictly convex polygon with \(n\) vertices located at integer coordinates \((x_1, y_1), \, (x_2, y_2), \, \dots, \, (x_n, y_n)\) of the plane.

The siblings have decided to eat the pizza in the following way: taking turns, starting with Alberto, each sibling chooses a vertex of the remaining part of the pizza and eats out the triangle determined by its two neighboring edges. In this way, after each of the first \(n - 3\) turns the pizza will have one less vertex. The game ends after the \((n - 2)\)-th turn, when all the pizza has been eaten.

Assuming that Alberto and Beatrice choose the slices to eat optimally, which of the siblings manages to eat at most half of the pizza? You should identify a sibling that has a strategy to do so and help them choose the slices appropriately. Note that it is possible that both Alberto and Beatrice end up eating exactly half of the area if they choose their slices optimally.

First, you should print a line containing either the string \(\texttt{Alberto}\) or the string \(\texttt{Beatrice}\) — the sibling that you will help to win.

Then, for the next \(n - 2\) turns, you will alternate with the judge in choosing a slice of the pizza and removing it, starting with you if you chose to help Alberto, or starting with the judge if you chose to help Beatrice.

• When it is your turn, print a single line containing an integer \(p\) (\(1 \leq p \leq n\)) that has not been chosen before, indicating that you want to eat the slice determined by the vertex located at \((x_p, y_p)\).
• When it is the judge's turn, read an integer \(q\) (\(1 \leq q \leq n\)), indicating that the other player eats the slice determined by the vertex located at \((x_q, y_q)\). It is guaranteed that \(q\) has not been chosen before.

If one of your interactions is malformed, the interactor terminates immediately and your program receives the verdict \(\texttt{WRONG-ANSWER}\). Otherwise, you will receive \(\texttt{CORRECT}\) if at the end your player has eaten at most half of the pizza, and \(\texttt{WRONG-ANSWER}\) otherwise.

After printing a line do not forget to end the line and flush the output. Otherwise, you will get the verdict \(\texttt{TIMELIMIT}\). To flush the output, use:

• \(\texttt{fflush(stdout)}\) in C;
• \(\texttt{fflush(stdout)}\), \(\texttt{cout <}\texttt{< flush}\) or \(\texttt{cout.flush()}\) in C++;
• \(\texttt{System.out.flush()}\) in Java and Kotlin;
• \(\texttt{sys.stdout.flush()}\) in Python.

У Монокарпа есть дерево, состоящее из \(n\) вершин.

Он планирует выбрать некоторую вершину \(r\) и проделать следующие операции над каждой вершиной \(v\) от \(1\) до \(n\):

• присвоить \(d_v\) равным расстоянию от \(v\) до \(r\) (количество ребер на кратчайшем пути);
• раскрасить \(v\) в какой-нибудь цвет.

Раскраска называется красивой, если она удовлетворяет двум условиям:

• для каждой пары вершин одного цвета \((v, u)\) существует путь из \(v\) в \(u\), который посещает только вершины того же цвета;
• для каждой пары вершины одного цвета \((v, u)\), \(d_v \neq d_u\).

Обратите внимание, что Монокарп может выбирать любое количество различных цветов, которые он хочет использовать.

Для каждого использованного цвета он затем считает количество вершин этого цвета. Стоимость дерева — это минимум из этих значений.

Какая может быть наибольшая стоимость дерева?