У Сони есть массив \(a_1, a_2, \ldots, a_n\) из \(n\) чисел и неотрицательное целое число \(x\). Ей нужно выполнить \(m\) запросов двух типов:

• \(1\) \(i\) \(y\): заменить \(i\)-й элемент на значение \(y\), то есть выполнить \(a_{i}\) := \(y\);
• \(2\) \(l\) \(r\): посчитать количество таких пар чисел (\(L\), \(R\)), что \(l\leq L\leq R\leq r\) и побитовое ИЛИ всех чисел подмассива \([L, R]\) не меньше \(x\) (обратите внимание, что \(x\) — константа для всех запросов).

Сможете ли вы помочь Соне выполнить все запросы?

Побитовое ИЛИ — это бинарная операция над парой неотрицательных целых чисел. Для подсчета побитового ИЛИ двух чисел надо рассмотреть запись обоих чисел в двоичной системе счисления. Результат — это такое число, в двоичном представлении которого в каждом разряде стоит единица если единица находится в двоичной записи хотя бы одного из аргументов. Например, \(10\) OR \(19\) = \(1010_2\) OR \(10011_2\) = \(11011_2\) = \(27\).

Вам дан прямоугольный параллелепипед с целыми положительными сторонами \(A\), \(B\) и \(C\).

Найдите количество различных троек целых чисел (\(a\), \(b\), \(c\)) таких, что \(1\leq a\leq b\leq c\) и параллелепипед \(A\times B\times C\) можно замостить параллелепипедами \(a\times b\times c\). Обратите внимание, что все замощающие параллелепипеды должны быть ориентированы в одну сторону.

Например, параллелепипед \(1\times 5\times 6\) можно разделить на параллелепипеды \(1\times 3\times 5\), но нельзя – на параллелепипеды \(1\times 2\times 3\).

Близится следующий сезон, поэтому Вы решили собрать команду из двух или трех человек. У Вас есть \(n\) кандидатов, \(i\)-й кандидат имеет ранг \(a_i\). Но у Вас есть какие-то странные ограничения: если Ваш ранг \(v\) и Вы выбрали кандидатов \(i\) и \(j\), то должно выполняться условие \(GCD(v, a_i) = X\) и \(LCM(v, a_j) = Y\).

Вы очень опытный участник, поэтому Вы можете сделать свой ранг любым неотрицательным целым числом, однако \(X\) и \(Y\) связаны с Вашим днем рождения, поэтому они фиксированы.

И вот Вы хотите узнать количество пар \((i, j)\) таких, что существует \(v\), что \(GCD(v, a_i) = X\) и \(LCM(v, a_j) = Y\). Разрешена ситуация \(i = j\), просто ваша команда будет состоять из двух участников.

\(GCD\) — это наибольший общий делитель двух чисел, а \(LCM\) — наименьшее общее кратное.

Общежитие состоит из \(m\) комнат, пронумерованных от \(0\) до \(m - 1\). Также в общежитии проживает \(x\)-мышь. \(x\)-мышь — это необычная мышь, так как \(x\)-мышь движется каждую секунду из комнаты \(i\) в комнату \(i \cdot x \mod{m}\) (фактически, телепортируется, так как не посещает никаких других комнат по дороге). Начальная позиция \(x\)-мыши неизвестна.

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

Единственное сделанное Вами наблюдение: \(\text{GCD} (x, m) = 1\).

У Алисы есть компьютер, который работает с \(w\)-битными целыми числами и имеет \(n\) регистров для чисел. Текущее содержимое регистров задано как массив \(a_1, a_2, \ldots, a_n\).

Компьютер использует так называемые «супер функции», каждая из которых принимает два входных регистра и считает некую функцию, используя те два регистра. Учтите, что вы можете использовать один и тот же регистр как два входных аргумента.

Каждая «супер функция» состоит из логических функций. Существует шесть логических функций: AND, OR, XOR, NOT AND, NOT OR и NOT XOR, которые обозначаются как «A», «O», «X», «a», «o», «x», соответственно. Каждая битовая функция принимает два входных бита. Их результаты с учетом входных данных \(b_1\), \(b_2\) приведены ниже:

«Супер функция», которая состоит из \(w\) логических операций, разделяет два входных числа \(x_1\) и \(x_2\) на \(w\) бит, выполняет \(i\)-ю логическую операцию с \(i\)-и битами двух входных чисел. После чего соединяет эти \(w\) бит и возвращает это число.

Например, для \(4\)-битного компьютера мы можем иметь функцию «AXoA» (AND, XOR, NOT OR, AND). Для двух входных чисел: \(13 = 1101_2\) и \(10 = 1010_2\), функция вернет \(12 = 1100_2\), так как \(1\) AND \(1\) равно \(1\), \(1\) XOR \(0\) равно \(1\), NOT (\(0\) OR \(1\)) равно \(0\) и \(1\) AND \(0\) равно \(0\).

Вам дан список всех \(m\) функций. Для каждой функции вам нужно найти количество упорядоченных пар переменных, которые на выходе дадут \(0\). Другими словами, найдите количество упорядоченных пар \((i,j)\), где \(1 \leq i,j \leq n\), таких что \(w_k(a_i, a_j) = 0\), где \(w_k\) — \(k\)-я функция, которую использует «супер функция».

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

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

Количество истоков в графе равно количеству стоков, и это число не превосходит \(20\).

К графу применяется следующий алгоритм:

1. если в графе нет истоков и стоков, то выйти;
2. выбрать произвольный исток \(s\), произвольный сток \(t\), добавить ребро из \(t\) в \(s\) в граф и перейти к шагу \(1\) (эта операция удаляет \(s\) из истоков и \(t\) из стоков). Обратите внимание, что \(s\) и \(t\) могут быть одной и той же вершиной, тогда добавляется петля.

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

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

В берляндском магазине есть \(n\) видов сока. Каждый сок характеризуется своей ценой \(c_i\), а также витаминами, которые в нём содержатся. В Берляндии есть всего три типа витаминов: витамин «A», витамин «B» и витамин «C». В каждом соке может быть один, два или все три витамина.

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

Задана таблица, состоящая из \(2\) строк и \(n\) столбцов. Каждая ячейка данной таблицы должна быть раскрашена либо в черный, либо в белый цвет.

Две ячейки являются соседями, если у них есть общая сторона и их цвет одинаков. Две ячейки \(A\) и \(B\) принадлежат одной и той же компоненте, если они являются соседями, или если существует сосед \(A\), который принадлежит к той же компоненте, что и \(B\).

Назовем некоторую двураскраску красивой, если у нее ровно \(k\) компонент из ячеек.

Посчитайте количество красивых двураскрасок. Это число может быть достаточно велико, поэтому выведите его по модулю \(998244353\).

Задано два целых числа \(l\) и \(r\) (\(l \le r\)). Ваша задача — посчитать сумму чисел от \(l\) до \(r\) (включая \(l\) и \(r\)) таких, что каждое число содержит не более \(k\) различных цифр, и вывести эту сумму по модулю \(998244353\).

Например, если \(k = 1\), тогда вам необходимо посчитать все числа от \(l\) до \(r\) такие, что каждое число содержит только одинаковые цифры. Для \(l = 10, r = 50\) ответ равен \(11 + 22 + 33 + 44 = 110\).

Задан массив \(a\), состоящий из \(n\) точек в \(k\)-мерном пространстве. Введем расстояние между двумя точками \(a_x\) и \(a_y\), как \(\sum \limits_{i = 1}^{k} |a_{x, i} - a_{y, i}|\) (также известное как манхэттенское расстояние).

Необходимо обработать \(q\) запросов двух следующих типов:

• \(1\) \(i\) \(b_1\) \(b_2\) ... \(b_k\) — выставить \(i\)-й элемент \(a\) равным точке \((b_1, b_2, \dots, b_k)\);
• \(2\) \(l\) \(r\) — найти максимальное расстояние между двумя точками \(a_i\) и \(a_j\), где \(l \le i, j \le r\).

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

Петр позвонил в свой автосалон и узнал, что должен повернуть колесо замка ровно \(n\) раз, причём \(i\)-й поворот должен составлять ровно \(a_i\) градусов. После всех \(n\) поворотов указатель должен снова указать на ноль.

Это немного озадачило Петра, так как он не знает, какие повороты следует сделать по часовой стрелке, а какие против. Так как есть много разных вариантов, помогите ему и узнайте, есть ли хотя бы один способ сделать все \(n\) поворотов так, чтобы указатель в конце снова указывал на ноль.

Последовательность Туе-Морса-Радецки-Матеуша (Туорса-Радевуша, для краткости) это бесконечная последовательность, получающаяся из конечной последовательности \(\mathrm{gen}\) длины \(d\) и целого числа \(m\), следующим образом:

• В начале мы определяем \(M_0=(0)\).
• На \(k\)-м шаге, \(k \geq 1\), мы определяем \(M_k\) как конкатенацию \(d\) копий \(M_{k-1}\). Однако, каждая из них немного изменяется — в \(i\)-й из них (\(1 \leq i \leq d\)) каждый элемент \(x\) заменяется на \((x+\mathrm{gen}_i) \pmod{m}\).

Например, если \(\mathrm{gen} = (0, \color{blue}{1}, \color{green}{2})\) и \(m = 4\):

• \(M_0 = (0)\),
• \(M_1 = (0, \color{blue}{1}, \color{green}{2})\),
• \(M_2 = (0, 1, 2, \color{blue}{1, 2, 3}, \color{green}{2, 3, 0})\),
• \(M_3 = (0, 1, 2, 1, 2, 3, 2, 3, 0, \color{blue}{1, 2, 3, 2, 3, 0, 3, 0, 1}, \color{green}{2, 3, 0, 3, 0, 1, 0, 1, 2})\), и так далее.

Как можно заметить, при условии, что первый элемент \(\mathrm{gen}\) равен \(0\), каждый последующий шаг порождает последовательность, префиксом которой является последовательность с предыдущего шага. Тогда мы можем определить бесконечную последовательность Туорса-Радевуша \(M_\infty\) как последовательность, получаемую бесконечным применением шага выше. Например, для параметров выше, \(M_\infty = (0, 1, 2, 1, 2, 3, 2, 3, 0, 1, 2, 3, 2, 3, 0, 3, 0, 1, \dots)\).

Матеуш выбрал последовательность \(\mathrm{gen}\) и целое число \(m\), и с помощью них получил последовательность Туорса-Радевуша \(M_\infty\). Затем он выбрал два целых числа \(l\) и \(r\) и записал подпоследовательность этой последовательности: \(A := ((M_\infty)_l, (M_\infty)_{l+1}, \dots, (M_\infty)_r)\).

Обратите внимание, что мы используем нумерацию с \(1\) для \(M_\infty\) и \(A\).

У Матеуша есть его любимая последовательность \(B\) длины \(n\) и хочет узнать, насколько она большая относительно \(A\). Он говорит, что последовательность \(B\) мажорирует последовательность \(X\) длины \(n\) (обозначим как \(B \geq X\)), если для всех \(i \in \{1, 2, \dots, n\}\) выполняется \(B_i \geq X_i\).

Теперь он спрашивает себя, сколько существует целых чисел \(x\) в отрезке \([1, |A| - n + 1]\) таких, что \(B \geq (A_x, A_{x+1}, A_{x+2}, \dots, A_{x+n-1})\). Так как обе последовательности очень большие, то ответить на вопрос, используя только бумагу и ручку, оказалось затруднительно. Не могли бы вы ему помочь?

Задана матрица \(a\), состоящая из \(n\) строк и \(m\) столбцов. В каждой ячейке записано целое число.

Разрешается произвольно изменить порядок строк (в том числе и оставить начальный порядок), но не разрешается менять порядок ячеек в строке. После того, как был выбран некоторый порядок строк, матрица полностью обходится следующим образом: сначала посещаются все ячейки первого столбца с верхней строки до нижней, потом так же все ячейки второго столбца и так далее. Во время обхода выписывается последовательность чисел в ячейках в том же порядке, в котором они были посещены. Назовем эту последовательность \(s_1, s_2, \dots, s_{nm}\).

Обход называется \(k\)-приемлемым, если для всех \(i\) (\(1 \le i \le nm - 1\)) \(|s_i - s_{i + 1}| \ge k\).

Найдите такое максимальное целое число \(k\) такое, что существует порядок строк матрицы \(a\), который образует \(k\)-приемлемый обход.

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

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

• \(1\) — Хиасат может поменять свой хендл.
• \(2\) \(s\) — друг \(s\) посещает профиль Хиасата.

Друг \(s\) будет счастлив, если каждый раз, когда он посетит страницу Хиасата, его хендл будет равен \(s\).

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

Вам дан массив \(a_1, a_2, \ldots, a_n\).

Необходимо выполнить \(q\) запросов следующих двух видов:

1. «MULTIPLY l r x» — для каждого \(i\) (\(l \le i \le r\)) нужно умножить \(a_i\) на \(x\).
2. «TOTIENT l r» — вычислить \(\varphi(\prod \limits_{i=l}^{r} a_i)\) по модулю \(10^9+7\), где \(\varphi\) обозначает функцию Эйлера.

Функцией Эйлера целого положительного числа \(n\) (обозначается как \(\varphi(n)\)) называется количество целых чисел \(x\) (\(1 \le x \le n\)), таких что \(\gcd(n,x) = 1\).

Задана строка длины \(n\). Каждый ее символ — это одна из \(p\) первых строчных латинских букв.

Также задана матрица \(A\) из бинарных значений размера \(p \times p\). Матрица симметрична (\(A_{ij} = A_{ji}\)). \(A_{ij} = 1\) обозначает, что \(i\)-я и \(j\)-я латинские буквы могут быть соседями в строке.

Назовем строку аккуратной, если все соседние символы в ней могут быть соседями (имеют 1 в соответствующей ячейке матрицы \(A\)).

Разрешается делать следующую операцию. Выбрать некоторую букву, удалить все ее вхождения и соединить оставшиеся части строки, не меняя их порядок. Например, после удаления буквы 'a' из «abacaba» останется «bcb».

Заданная строка аккуратная. Строка должна оставаться аккуратной после каждой сделанной операции.

Разрешается делать произвольное число операций (возможно ноль). Какую самую короткую строку можно получить в результате?

Заданы две строки \(s\) и \(t\), обе состоят ровно из \(k\) строчных букв латинского алфавита, \(s\) лексикографически меньше \(t\).

Рассмотрим список всех строк, состоящих ровно из \(k\) строчных латинских букв, лексикографически не меньших, чем \(s\) и не больше, чем \(t\) (включая \(s\) и \(t\)) в лексикографическом порядке. Например, для \(k=2\), \(s=\)«az» и \(t=\)«bf» список будет равен [«az», «ba», «bb», «bc», «bd», «be», «bf»].

Ваша задача — вывести медиану (средний элемент) этого списка. Для примера выше это будет «bc».

Гарантируется, что количество строк, лексикографически не меньших, чем \(s\) и не больших, чем \(t\), нечетно.

Есть взвешенное дерево с \(n\) вершинами и \(n-1\) ребрами. Вершины пронумерованные от \(1\) до \(n\). Веса ребер — положительные целые числа не превышающее \(100\). Определим расстояние между двумя вершинами как сумму ребер на уникальном пути между ними. Вы хотели бы найти диаметр дерева. Диаметр — это максимальное расстояние между вершинами.

К сожалению, дерево вам неизвестно, но вы можете задать несколько вопросов. В одном вопросе вы можете указать два непустых непересекающихся набора вершин \(p\) и \(q\), и вам скажут максимальное расстояние между одной вершиной в \(p\) и одной вершиной в \(q\). Другими словами, максимальное расстояние между \(x\) и \(y\), где \(x \in p\) и \(y \in q\). Задав не более \(9\) вопросов, вы должны найти максимальное расстояние между любой парой вершин.

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

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

Чтобы задать вопрос, выведите «\(k_1\ k_2\ a_1\ a_2\ \ldots\ a_{k_1}\ b_1\ b_2\ \ldots\ b_{k_2}\)» \((k_1, k_2 \geq 1\) и \(k_1+k_2 \leq n\)). Эти два множества не должны быть пусты и не должны пересекаться. В ответ считайте одно целое число \(\max_{p,q} dist(a_p, b_q)\). Если вы когда-либо получите \(-1\), немедленно завершите вашу программу, чтобы избежать других вердиктов.

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

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

Когда вы будете готовы ответить, выведите «\(-1\ d\)», где \(d\) — максимальное кратчайшее расстояние по всем парам вершин.

Вы можете задать не более \(9\) вопросов в каждом тесте.

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

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

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

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

Каждая из следующих \(n-1\) строк должна содержать три целых числа \(a_i, b_i, c_i\) (\(1\leq a_i, b_i\leq n\), \(1 \leq c_i \leq 100\)). Они описывают неориентированное ребро между вершинами \(a_i\) и \(b_i\) с весом \(c_i\). Эти ребра должны образовывать дерево.

Вам дано \(n\) объектов. У каждого объекта есть два целочисленных свойства: \(val_i\) — его цена — и \(mask_i\). Гарантируется, что изначально сумма цен всех объектов не равна нулю.

Вы хотите выбрать некоторое целое положительное число \(s\). После этого все объекты модифицируется, причем \(i\)-й объект модифицируется следующим образом:

• рассмотрим \(mask_i\) и \(s\) в двоичной системе счисления,
• вычислим побитовое «И» \(s\) и \(mask_i\) (\(s \,\&\, mask_i\)),
• если (\(s \,\&\, mask_i\)) содержит нечётное число единиц в двоичной записи, то \(val_i\) меняется на \(-val_i\). Иначе с \(i\)-м объектом ничего не происходит.

Нужно найти такое целое число \(s\), что если произвести модификацию, как описано выше, то сумма всех цен сменит знак (если она была отрицательной, то она должна стать положительной, и наоборот; не разрешается сумме становится нулём). При этом абсолютное значение суммы цен может стать любым.

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

Предположим у нас есть кошка с целым числом \(x\). Идеальная длинная кошка это кошка с числом равным \(2^m - 1\) для некоторого неотрицательного \(m\). Например числа \(0\), \(1\), \(3\), \(7\), \(15\) подходят для идеальных длинных кошек.

В кошачьем преобразовании фурфурье можно менять \(x\) используя следующие операции:

• (Операция А): вы выбираете произвольное неотрицательное число \(n\) и заменяете \(x\) на \(x \oplus (2^n - 1)\), где \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
• (Операция Ы): заменить \(x\) на \(x + 1\).

Первая применённая операция должна быть типа А, вторая операция — типа Ы, третья снова типа А, и так далее. Формально, если пронумеровать операции с единицы в порядке их выполнения, то операции с нечётным номером должны быть типа А, а операции с чётным номером — типа Ы.

Неко хочет производит идеальных длинных кошек в промышленном масштабе, поэтому на одну кошку он может потратить не более \(40\) операций. Можете ли вы ему помочь и составить план операций, которые нужно проделать?

Обратите внимание, что не требуется минимизировать число выполненных операций. Достаточно лишь, чтобы число операций не превосходило \(40\).

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

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

Кошковселенная состоит из \(n\) планет, пронумерованных от \(1\) до \(n\). В начале игры Аки выбирает планету, на которой изначально находится Неко. Затем Аки совершает \(k - 1\) ходов, где за один ход Аки перемещает Неко с текущей планеты \(x\) на какую-то планету \(y\), такую что:

• Планета \(y\) ещё не посещена.
• \(1 \leq y \leq x + m\) (где \(m\) это фиксированная константа, заданная во входных данных)

Таким образом Неко посетит ровно \(k\) различных планет. Два способа посещений планет называются различными, если существует индекс \(i\), что \(i\)-я планета в первом способе отличается от \(i\)-й планеты во втором способе.

Сколько всего существует способов посетить \(k\) планет таким образом? Так как ответ может быть достаточно большим, выведите его по модулю \(10^9 + 7\).

Даша-путешественница решила использовать все заработанные за несколько лет отчисления на шоппинг. А где же еще лучше магазины, чем в Нлогонии?

Всего в Нлогонии \(n\) магазинов, пронумерованных от \(1\) до \(n\). В \(i\)-м из этих магазинов можно купить положительное целое число \(a_i\).

В каждый из последних \(m\) дней Даша покупала по одному числу в некоторых магазинах. В каждый из этих дней лисенок Жулик покупал по одному числу во всех магазинах, в которых Даша не купила число в этот день.

Дора считает, что Жулик соперничает с ней; она считает, что выиграла у Жулика в день \(i\), если и только если наименьшее общее кратное чисел, которые она купила в \(i\)-й день строго больше наименьшего общего кратного чисел, которые купил в \(i\)-й день Жулик.

Наименьшем общем кратном (НОК) набора целых чисел называется наименьшее положительное целое число, делящееся на все числа из набора.

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

Обратите внимание, возможно, что некоторые значения \(a_i\) в решении совпадают.

Даны два числа \(n\) и \(x\), найдите массив, который удовлетворяет следующим условиям:

• для любого числа \(a_i\) в массиве выполняется \(1 \le a_i<2^n\),
• нет такого непустого подотрезка, на котором побитовое исключающее ИЛИ равно \(0\) или \(x\),
• длина массива \(l\) должна быть максимальна.

Последовательность \(b\) является подотрезком \(a\), если \(b\) может быть получена из \(a\) удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца.

Единственное отличие этой версии от усложнённой — это ограничения.

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

В плеере у Поликарпа хранится \(n\) песен, причем каждая из них характеризуется двумя параметрами: \(t_i\) и \(g_i\), где \(t_i\) — длительность песни в минутах (\(1 \le t_i \le 15\)), \(g_i\) — её жанр (\(1 \le g_i \le 3\)).

Поликарп хочет составить такой плейлист, чтобы всё время в пути от университета до дома, он мог слушать музыку и в момент прибытия домой плейлист кончился. Поликарп никогда не прерывает песни и всегда слушает их от начала и до конца. Таким образом, если он начал слушать \(i\)-ю песню, то на её прослушивание он потратит ровно \(t_i\) минут. Также Поликарп не любит, когда подряд играют две песни одинакового жанра или когда песни в его плейлисте повторяются.

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

Вам заданы две бинарные строки \(x\) и \(y\), которые являются двоичными представлениями некоторых чисел (назовем их \(f(x)\) и \(f(y)\)). Вы можете выбрать целое число \(k \ge 0\), посчитать значение \(s_k = f(x) + f(y) \cdot 2^k\) и выписать двоичное представление \(s_k\) в обратном порядке (назовем его \(rev_k\)). Например, пусть \(x = 1010\) и \(y = 11\); вы выбрали \(k = 1\), и так как \(2^1 = 10_2\), то \(s_k = 1010_2 + 11_2 \cdot 10_2 = 10000_2\) и \(rev_k = 00001\).

Для заданных \(x\) и \(y\), вам необходимо выбрать такое целое \(k\), что \(rev_k\) — лексикографически минимально (прочтите примечание, если не знаете, что означает «лексикографически»).

Гарантируется, что при заданных ограничениях \(k\) существует и конечно.

Это интерактивная задача. Не забывайте о том, что ваша программа должна каждый раз после вывода запроса сбрасывать буфер вывода. Для сброса буфера вывода можно использовать fflush(stdout) в C++, system.out.flush() в Java, stdout.flush() в Python или flush(output) в Pascal. Если вы используете другой язык программирования, посмотрите в его документации, как выполняется эта операция. Также рекомендуем вам прочесть руководство по интерактивным задачам: https://cf.m27.workers.dev/blog/entry/45307.

Мы загадали целое число \(x\), не меньше \(0\) и не больше \(2^{14} - 1\). Вы должны угадать это число.

Для этого вы можете задать не более \(2\) запросов. Каждый запрос должен состоять из \(100\) целых чисел \(a_1\), \(a_2\), ..., \(a_{100}\) (каждое число должно быть не меньше \(0\) и не больше \(2^{14} - 1\)). В ответ на запрос мы выберем целое число \(i\) (\(1 \le i \le 100\)) и сообщим вам значение \(a_i \oplus x\) (побитовое исключающее ИЛИ чисел \(a_i\) и \(x\)). Все \(200\) чисел, которые вы используете в запросах, обязательно должны быть различны.

Гарантируется, что значение \(x\) в каждом тесте зафиксировано, но выбор числа \(i\) в каждом запросе может зависеть от того, какие числа вы посылаете.

До того, как ваша программа даст ответ, она может отправить не более \(2\) запросов. Чтобы отправить запрос, выведите строку следующего формата: \(?\) \(a_1\) \(a_2\) ... \(a_{100}\), где каждое \(a_j\) должно быть целым числом из отрезка \([0, 2^{14} - 1]\). Строка, которую вы отправляете, должна заканчиваться символов перевода строки. После отправки запроса программа должна сбросить буфер вывода и прочитать ответ на запрос — значение \(a_i \oplus x\) для некоторого \(i \in [1, 100]\). Никакое число не должно быть использовано в запросах дважды, ни в пределах одного и того же запроса, ни в разных запросах.

Если вы зададите некорректный запрос (или же количество запросов превысит \(2\)), ответом будет число \(-1\). Если ваша программа получила такой ответ, она должна немедленно завершиться — иначе вы можете получить вердикт «Ошибка исполнения», «Превышено ограничение времени» или какой-нибудь другой, а не «Неправильный ответ».

Это более лёгкая версия следующей задачи, отличающаяся от неё только ограничениями.

Вам дана прямоугольная матрица \(a\) размером \(n \times m\). За один ход вы можете выбрать произвольный столбец и циклически сдвинуть все элементы в этом столбце. Вы можете выполнять эту операцию произвольное (ноль или более) количество раз. Вы можете применять эту операцию для одного столбца произвольное количество раз.

После того, как вы закончили, вы вычисляете для каждой строки наибольший элемент в ней. Предположим, для \(i\)-й строки он равен \(r_i\). Чему равно наибольшее значение \(r_1+r_2+\ldots+r_n\)?

Недавно биологами было сделано удивительное открытие, позволяющее определять в каком настроении находится хамелеон. Для простоты будем считать, что туловище хамелеона имеет вид таблицы размером \(n \times m\), каждая клетка которой может быть зеленой или синей и изменять свой цвет. Будем обозначать за \((x, y)\) (\(1 \leq x \leq n\), \(1 \leq y \leq m\)) клетку, которая находится в строке с номером \(x\) и столбце с номером \(y\).

Будем называть признаком хорошего настроения хамелеона такую четверку клеток, являющихся угловыми клетками некоторого прямоугольника внутри таблицы, что цвета клеток в противоположных углах совпадают, но при этом не все четыре клетки одного цвета. Более формально, это четверка клеток \((x_1, y_1)\), \((x_1, y_2)\), \((x_2, y_1)\), \((x_2, y_2)\) для некоторых \(1 \leq x_1 < x_2 \leq n\), \(1 \leq y_1 < y_2 \leq m\), что цвета \((x_1, y_1)\) и \((x_2, y_2)\) совпадают и цвета \((x_1, y_2)\) и \((x_2, y_1)\) совпадают, но при этом не все четыре клетки имеют одинаковый цвет. Было обнаружено, что если такая четверка клеток существует, то у хамелеона хорошее настроение; в противном случае настроение хамелеона плохое.

Вас просят помочь учёным написать программу, которая определяет настроение хамелеона. Будем считать, что изначально хамелеон полностью зеленый, то есть все клетки таблицы имеют зеленый цвет. После этого окраска хамелеона может несколько раз измениться. За один раз цвет клеток некоторого отрезка одной строки таблицы может измениться на противоположный. Более формально, каждое изменение окраски хамелеона задается числами \(a\), \(l\), \(r\) (\(1 \leq a \leq n\), \(1 \leq l \leq r \leq m\)). При этом цвет всех клеток \((a, b)\), таких, что \(l \leq b \leq r\), меняется на противоположный.

Напишите программу, которая после каждого изменения окраски будет сообщать настроение хамелеона. При этом, если настроение хамелеона хорошее, то программа должна сообщать любые подходящие \(x_1\), \(y_1\), \(x_2\), \(y_2\), такие, что четверка клеток \((x_1, y_1)\), \((x_1, y_2)\), \((x_2, y_1)\), \((x_2, y_2)\) является признаком хорошего настроения.

Вам задана бинарная строка \(s\) (эта строка содержит только цифры \(0\) и \(1\)).

Пусть \(f(t)\) — десятичное представление числа \(t\), записанного в двоичном виде (возможно с лидирующими нулями). Например \(f(011) = 3, f(00101) = 5, f(00001) = 1, f(10) = 2, f(000) = 0\) и \(f(000100) = 4\).

Подстрока \(s_{l}, s_{l+1}, \dots , s_{r}\) хорошая, если \(r - l + 1 = f(s_l \dots s_r)\).

Например, строка \(s = 1011\) имеет \(5\) хороших подстрок: \(s_1 \dots s_1 = 1\), \(s_3 \dots s_3 = 1\), \(s_4 \dots s_4 = 1\), \(s_1 \dots s_2 = 10\) и \(s_2 \dots s_4 = 011\).

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

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

Вам задан неориентированный граф из \(n\) вершин и \(m\) ребер. Вы должны написать число на каждой вершине графа, каждое число должно быть равно \(0\) или \(1\). После этого на каждом ребре будет записана сумма чисел на двух вершинах, инцидентных этому ребру.

Вы должны выбрать числа таким образом, чтобы было хотя бы одно ребро с числом \(0\), хотя бы одно ребро с числом \(1\) и хотя бы одно ребро с числом \(2\). Сколько способов так расставить числа? Два способа различны, если существует хотя бы одна вершина, на которой в разных способах записаны разные числа.

На доске написано \(n\) положительных чисел. Также выбрано положительное число \(k \geq 2\), и ни одно из написанных чисел не делится на \(k\). За одну операцию разрешается стереть с доски любые два числа \(x\) и \(y\) и записать вместо них \(f(x + y)\), где \(f(x)\) равно \(x\), если \(x\) не делится на \(k\), и \(f(x) = f(x / k)\) в противном случае.

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

У вас есть пароль, который вы часто набираете — строка \(s\) длины \(n\), состоящая из первых \(m\) букв латинского алфавита.

Из-за того, что вы много времени тратите на набор этого пароля, вы хотите купить новую клавиатуру.

Клавиатура — это перестановка первых \(m\) букв латинского алфавита. Например, если \(m = 3\), то существует всего шесть различных клавиатур: abc, acb, bac, bca, cab и cba.

Так как вы набираете пароль одним пальцем, вам нужно тратить время на перемещение этого пальца от одного символа пароля к другому. Время перемещения пальца от символа \(s_i\) к символу \(s_{i+1}\) равно дистанции между этими символами на клавиатуре. Суммарное потраченное время на набор пароля называется медлительностью.

Формально, медлительность клавиатуры равна \(\sum\limits_{i=2}^{n} |pos_{s_{i-1}} - pos_{s_i} |\), где \(pos_x\) — позиция символа \(x\) на клавиатуре.

Например, если \(s\) = aacabc, а клавиатура равна bac, то медлительность клавиатуры равна \(|pos_a - pos_a| + |pos_a - pos_c| + |pos_c - pos_a| + |pos_a - pos_b| + |pos_b - pos_c|\) = \(|2 - 2| + |2 - 3| + |3 - 2| + |2 - 1| + |1 - 3|\) = \(0 + 1 + 1 + 1 + 2 = 5\).

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

В ходе проведения очередной весенней уборки, Даниэль нашел старый калькулятор, который ему очень понравился. Однако кажется, что что-то в нем сломано. Когда он хочет посчитать \(1 + 3\) c помощью калькулятора, он получает \(2\) вместо \(4\). Но при вычислении \(1 + 4\) ответ получается правильный, \(5\). Озадаченный таким поведением, он вскрыл калькулятор и нашел разгадку: полные сумматоры стали полусумматорами!

Теперь, когда он хочет посчитать \(a + b\) при помощи калькулатора, он получает ксор-сумму \(a \oplus b\) (определение можно прочитать по ссылке: https://ru.wikipedia.org/wiki/Сложение_по_модулю_2).

Но как он уже заметил ранее, калькулятор иногда выдает правильные ответы. Поэтому его интересует, при данных \(l\) и \(r\) сколько существует таких пар целых чисел \((a, b)\), для которых выполняются следующие условия: \(\)a + b = a \oplus b\(\) \(\)l \leq a \leq r\(\) \(\)l \leq b \leq r\(\)

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

Вам заданы два множества: \(A\) и \(B\). Найдите сумму элементов в множестве \(C = \{x | x = a \oplus b, a \in A, b \in B\}\), по модулю \(998244353\), где \(\oplus\) означает операцию побитовое исключающее ИЛИ. Каждое число должно быть посчитано ровно один раз.

Например, если \(A = \{2, 3\}\) и \(B = \{2, 3\}\) вы должны учесть число \(1\) только один раз, несмотря на то, что вы можете получить его как \(3 \oplus 2\) и как \(2 \oplus 3\). Таким образом, ответ в этом случае будет равен \(1 + 0 = 1\).

Будем называть отрезком \([l; r]\) множество целых чисел вида \(\{l, l+1, \dots, r\}\).

Множество \(A\) задано объединением \(n_A\) отрезков, множество \(B\) задано объединением \(n_B\) отрезков.

Сегодня Бакри в качестве дружеского подарка вручил Бадави \(n\) целых чисел \(a_1, a_2, \dots, a_n\) и дал ему задачку выбрать такой \(X\), что \(\underset{1 \leq i \leq n}{\max} (a_i \oplus X)\) принимает минимальное возможное значение, где \(\oplus\) обозначает операцию побитового исключающего ИЛИ.

Бадави, как обычно, ленится, поэтому вы решили помочь ему и найти минимальное возможное значение \(\underset{1 \leq i \leq n}{\max} (a_i \oplus X)\).

Давным давно, семилетняя Нора любила играть в игрушки вместе со своим созданием ROBO_Head-02, не только для того чтобы развлечься, но и чтобы улучшить его способности.

Однажды, приёмный отец Норы, Феникс Уайл, принёс Норе \(n\) коробок с игрушками. Перед тем как их распаковать, Нора решила устроить для ROBO небольшую игру.

Она пронумеровала все \(n\) коробок используя \(n\) различных целых чисел \(a_1, a_2, \ldots, a_n\) и попросила ROBO выполнить ноль или более операций следующего вида:

• Выбрать три различных индекса \(i\), \(j\) и \(k\), таких что \(a_i \mid a_j\) и \(a_i \mid a_k\). Иными словами, \(a_i\) делит и \(a_j\), и \(a_k\). Иначе говоря, \(a_j \bmod a_i = 0\), \(a_k \bmod a_i = 0\).
• Затем, Нора передаст \(k\)-ю коробку ROBO, а тот положит её наверх стопки с коробками рядом с ним. Изначально эта стопка пуста.
• После этого коробка \(k\) становится недоступной для любых дальнейших действий.

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

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

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

This is an unusual problem in an unusual contest, here is the announcement: http://cf.m27.workers.dev/blog/entry/73543

You have the safe lock which consists of 5 decimal digits. If you rotate some digit, it increases by one, except 9 which becomes 0.

Initially, the lock contains number \(x\). To unlock the safe you must do the following operations in order (and be careful, don't mix up if and else statements).

If sum of digits on positions 1 and 4 is greater than 10, rotate digit on position 1 by 3 times, else rotate digit on position 4 by 8 times.

If sum of digits on positions 3 and 2 is greater than 8, rotate digit on position 4 by 9 times, else rotate digit on position 5 by 8 times.

If digit on position 3 is odd, rotate digit on position 3 by 3 times, else rotate digit on position 3 by 4 times.

If digit on position 5 is greater than digit on position 2, rotate digit on position 4 by 1 times, else rotate digit on position 2 by 7 times.

If digit on position 1 is odd, rotate digit on position 1 by 3 times, else rotate digit on position 3 by 5 times.

If digit on position 4 is odd, rotate digit on position 4 by 7 times, else rotate digit on position 1 by 9 times.

If digit on position 4 is greater than digit on position 1, rotate digit on position 4 by 9 times, else rotate digit on position 4 by 2 times.

If digit on position 1 is greater than digit on position 3, rotate digit on position 2 by 1 times, else rotate digit on position 3 by 1 times.

If digit on position 5 is greater than digit on position 3, rotate digit on position 4 by 5 times, else rotate digit on position 5 by 8 times.

If sum of digits on positions 1 and 3 is greater than 8, rotate digit on position 4 by 5 times, else rotate digit on position 2 by 5 times.

If digit on position 1 is greater than digit on position 4, rotate digit on position 4 by 3 times, else rotate digit on position 2 by 3 times.

If sum of digits on positions 3 and 1 is greater than 9, rotate digit on position 2 by 9 times, else rotate digit on position 2 by 2 times.

If sum of digits on positions 4 and 3 is greater than 10, rotate digit on position 4 by 7 times, else rotate digit on position 5 by 7 times.

If digit on position 3 is greater than digit on position 2, rotate digit on position 3 by 2 times, else rotate digit on position 4 by 6 times.

If digit on position 1 is greater than digit on position 3, rotate digit on position 1 by 9 times, else rotate digit on position 2 by 9 times.

If digit on position 3 is odd, rotate digit on position 3 by 9 times, else rotate digit on position 1 by 5 times.

If sum of digits on positions 3 and 5 is greater than 9, rotate digit on position 3 by 4 times, else rotate digit on position 3 by 9 times.

If digit on position 3 is greater than digit on position 1, rotate digit on position 5 by 1 times, else rotate digit on position 5 by 7 times.

If digit on position 1 is greater than digit on position 3, rotate digit on position 2 by 9 times, else rotate digit on position 4 by 6 times.

If sum of digits on positions 2 and 3 is greater than 10, rotate digit on position 2 by 2 times, else rotate digit on position 3 by 6 times.

Курони плохо разбирается в экономике. Поэтому он решил основать новую финансовую пирамиду под названием Антихайп. У него есть следующие правила:

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

\(n\) людей недавно услышали об Антихайпе, возраст \(i\)-го человека - \(a_i\). Некоторые из них являются друзьями, но дружба сегодня  — странная вещь: \(i\)-й человек является другом \(j\)-го человека тогда и только тогда, когда \(a_i \text{ AND } a_j = 0\), где \(\text{AND}\) обозначает операцию побитового И.

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

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

Сегодня дед Мороз пришел на праздник и перед ним выстроились \(m\) детей. Пронумеруем их от \(1\) до \(m\). Дед Мороз знает \(n\) заклинаний. Заклинание под номером \(i\) даёт по конфете каждому ребенку, чье место лежит в отрезке \([L_i, R_i]\). Каждое заклинание может быть использовано не более одного раза. Также известно, что если применить все заклинания, то каждый ребёнок получит не более \(k\) конфет.

Детям вредно есть много сладкого, поэтому каждый ребёнок может съесть не более одной конфеты, а остальное отдаст маме и папе в равном количестве. Получается, если конфет малышу не подарить или подарить ему чётное число конфет, то он не съест ни одной конфеты и уйдет печальным. Остальные же дети (которые получили нечётное число конфет) будут счастливыми.

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

На восьмое марта Катерине подарили массив чисел. Со временем ей стало скучно просто смотреть на него, и она решила посчитать некоторые его бесполезные характеристики. Со всеми, что она придумывала, ей это удавалось. Придумав очередную — xor попарных сумм чисел в массиве, она поняла, что не может придумать, как посчитать её для большого массива, и попросила вас помочь. А вы сможете? Более формально, вам нужно посчитать

\(\) (a_1 + a_2) \oplus (a_1 + a_3) \oplus \ldots \oplus (a_1 + a_n) \\ \oplus (a_2 + a_3) \oplus \ldots \oplus (a_2 + a_n) \\ \ldots \\ \oplus (a_{n-1} + a_n) \\ \(\)

Запись \(x \oplus y\) обозначает битовый XOR чисел (т.е. \(x\) ^ \(y\) для многих современных языков программирования). Об этой операции вы можете прочитать по ссылке в Wikipedia: https://tiny.cc/34xykz.

Для данных 2 чисел \(u\) и \(v\), найдите самые короткий массив такой, что побитовое исключающее ИЛИ его элементов равно \(u\), а сумма его элементов равна \(v\).

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

\(n\) мудрецов живут в красивом городе. Некоторые из них знают друг друга.

Для всех возможных \(n!\) перестановок \(p_1, p_2, \ldots, p_n\) мудрецов, построим бинарную строку длины \(n-1\): для всех \(1 \leq i < n\) положим \(s_i=1\) если мудрецы \(p_i\) и \(p_{i+1}\) знают друг друга, и \(s_i=0\) иначе.

Для всех \(2^{n-1}\) возможных бинарных строк, найдите число перестановок, при которых получается такая бинарная строка.

Вам даны строка \(S\) и массив строк \([t_1, t_2, \dots, t_k]\). Каждая строка \(t_i\) состоит из строчных латинских букв от a до n; \(S\) состоит из строчных латинских букв от a до n и не более \(14\) знаков вопроса.

У каждой строки \(t_i\) есть цена \(c_i\) — целое число. Стоимость некоторой строки \(T\) считается как \(\sum\limits_{i = 1}^{k} F(T, t_i) \cdot c_i\), где \(F(T, t_i)\) — количество вхождений \(t_i\) в \(T\) в качестве подстроки. К примеру, \(F(\text{aaabaaa}, \text{aa}) = 4\).

Вы должны заменить все знаки вопроса в \(S\) на попарно различные строчные латинские буквы от a до n так, чтобы стоимость \(S\) была максимально возможной.

Дана перестановка \(p\), состоящая из \(26\) целых чисел от \(1\) до \(26\) (так как это перестановка, каждое число от \(1\) до \(26\) встречается в \(p\) ровно один раз), а также две строки \(s\) и \(t\), состоящие из строчных букв латинского алфавита.

Подстрока \(t'\) строки \(t\) является вхождением строки \(s\), если выполняются следующие условия:

1. \(|t'| = |s|\);
2. для каждого \(i \in [1, |s|]\) либо \(s_i = t'_i\), либо \(p_{idx(s_i)} = idx(t'_i)\), где \(idx(c)\) — номер символа \(c\) в латинском алфавите (\(idx(\text{a}) = 1\), \(idx(\text{b}) = 2\), \(idx(\text{z}) = 26\)).

Например, если \(p_1 = 2\), \(p_2 = 3\), \(p_3 = 1\), \(s = \text{abc}\), \(t = \text{abcaaba}\), три подстроки \(t\) являются вхождениями \(s\) (\(t' = \text{abc}\), \(t' = \text{bca}\) и \(t' = \text{aba}\)).

Для каждой подстроки \(t\) с длиной, равной \(|s|\), проверьте, является ли она вхождением строки \(s\).

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

Chiori очень любит куклы и сейчас она собирается украсить свою спальню!

Так как Chiori коллекционирует куклы, всего у нее \(n\) кукол, \(i\)-я из этих кукол имеет неотрицательное целое число \(a_i\) (\(a_i < 2^m\), \(m\) дано). Chiori хочет выбрать некоторых кукол (возможно ноль) для украшения. Таким образом, всего существует \(2^n\) способов.

Обозначим за \(x\) побитовую xor сумму значений у кукол, выбранных Chiori (в случае, если Chiori не выбрала ни одной куклы, \(x = 0\)). Значением способа выбора кукол назовем количество битов равных \(1\) в двоичном представлении \(x\). Более формально, это число также равно количеству индексов \(0 \leq i < m\), таких что \(\left\lfloor \frac{x}{2^i} \right\rfloor\) нечетно.

Посчитайте для Chiori количество способов выбрать куклы со значением \(i\) для всех целых \(i\) от \(0\) до \(m\). Поскольку эти числа могут быть очень большими, вы должны посчитать их по модулю \(998\,244\,353\).

Рассмотрим бесконечную последовательность \(s\) натуральных чисел, построенную повторением следующих шагов:

1. Найдите лексикографически наименьшую тройку натуральных чисел \((a, b, c)\) такую, ​​что
   • \(a \oplus b \oplus c = 0\), где \(\oplus\) обозначает побитовое исключающее ИЛИ.
   • \(a\), \(b\), \(c\) не находятся в \(s\).
   Здесь тройка целых чисел \((a_1, b_1, c_1)\) считается лексикографически меньше тройки \((a_2, b_2, c_2)\), если последовательность \([a_1, b_1, c_1]\) лексикографически меньше последовательности \([a_2, b_2, c_2]\)
2. Добавьте \(a\), \(b\), \(c\) в конец \(s\) в этом порядке.
3. Вернитесь к первому шагу.

У вас есть целое число \(n\). Найдите \(n\)-й элемент \(s\).

Вы должны ответить на \(t\) независимых тестовых случаев.

Последовательность \(a\) лексикографически меньше последовательности \(b\), если в первой позиции, где \(a\) и \(b\) различны, в последовательности \(a\) элемент меньше, чем соответствующий элемент в \(b\).

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

Во время каждой операции вы выбираете два индекса \(i\) и \(j\) (\(1 \le i, j \le n\); \(i \ne j\)), увеличиваете \(a_j\) на \(a_i\), а затем удаляете \(i\)-й элемент из массива (при этом индексы всех элементов правее удаляемого уменьшаются на \(1\), и размер массива \(n\) также уменьшается на \(1\)).

Ваша цель — сделать массив \(a\) строго возрастающим, то есть должно выполняться условие \(a_1 < a_2 < \dots < a_n\) (где \(n\) — итоговый размер массива).

Посчитайте минимальное количество операций, которое требуется, чтобы массив стал возрастающим.

Рассмотрим все двоичные строки длины \(m\) (\(1 \le m \le 60\)), то есть строки, состоящие из символов 0 и 1. Например, 0110 является двоичной строкой, а 012aba — нет. Очевидно, что всего таких строк ровно \(2^m\).

Строка \(s\) лексикографически меньше строки \(t\) (обе имеют одинаковую длину \(m\)), если в первой слева позиции \(i\), в которой они отличаются, верно \(s[i] < t[i]\). Именно такой способ сравнения строк используется в словарях и в большинстве современных языков программирования при их сравнении стандартным способом. Например, строка 01011 лексикографически меньше строки 01100, потому что первые два символа совпадают, а третий символ в первой строке меньше, чем во второй.

Удалим из этого множества \(n\) (\(1 \le n \le \min(2^m-1, 100)\)) различных двоичных строк \(a_1, a_2, \ldots, a_n\), каждая длины \(m\). Таким образом, в множестве останется \(k=2^m-n\) строк. Отсортируем все строки полученного множества в порядке лексикографического возрастания (как в словаре).

Пронумеруем все строки после сортировки от \(0\) до \(k-1\). Выведите строку, номер которой равен \(\lfloor \frac{k-1}{2} \rfloor\) (такой элемент называется медианой), где \(\lfloor x \rfloor\) является округлением числа вниз к ближайшему целому.

Например, если \(n=3\), \(m=3\) и \(a=[\)010, 111, 001\(]\), то после удаления строк \(a_i\) и сортировки результат примет вид: \([\)000, 011, 100, 101, 110\(]\). Таким образом, искомая медиана равна 100.

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

На столе его отца хранится множество \(S\), содержащее очень важные числа. В момент, когда Джонни узнал об этом, он решил, что это хорошая идея выбрать положительное целое число \(k\) и заменить все элементы \(s\) из множества \(S\) на \(s \oplus k\) (\(\oplus\) обозначает операцию исключающего или).

Помогите Джонни выбрать такое \(k\), что его отец не заметит никакой разницы после того, как Джонни закончит играть (т.е. Джонни должен получить такое же множество, какое было изначально). Возможно, что ни одного такого числа не существует. Также, возможно, что существует несколько подходящих чисел. В таком случае, выведите минимальное из них. Обратите внимание, что порядок элементов в множестве не имеет значения, т.е. множество \(\{1, 2, 3\}\) равно множеству \(\{2, 1, 3\}\).

Формально, требуется найти минимальное положительное целое число \(k\), такое что \(\{s \oplus k | s \in S\} = S\) или сообщить, что ни одного подходящего числа не существует.

Например, если \(S = \{1, 3, 4\}\) и \(k = 2\), новое множество будет равно \(\{3, 1, 6\}\). Если \(S = \{0, 1, 2, 3\}\) и \(k = 1\), после игры множество останется таким же.

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

У Ехаба есть загаданная перестановка \(p\) длины \(n\), состоящая из элементов от \(0\) до \(n-1\). По какой-то причине вы хотите выяснить перестановку. Для этого вы можете спросить у Ехаба \(2\) разных индекса \(i\) и \(j\), и он ответит \((p_i|p_j)\), где \(|\) обозначает операцию побитового ИЛИ.

У Ехаба есть достаточно свободного времени, чтобы ответить на \(4269\) вопросов, и, несмотря на то, что ему несложно отвечать на так много вопросов, ему лень играть в ваши глупые игры, поэтому он заранее зафиксирует перестановку и не изменит ее в зависимости от ваших запросов. Можете ли вы угадать перестановку?

Чтобы задать вопрос, выведите "? \(i\) \(j\)" (без кавычек, \(i \neq j\)) Затем вы должны считать ответ, который будет равен \((p_i|p_j)\).

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

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

Чтобы дать ответ, выведите "! \(p_1\) \(p_2\) \(\ldots\) \(p_n\)" (без кавычек). Заметьте, что вывод ответа не считается одним из \(4269\) запросов.

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

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

Взломы:

Первая строка должна содержать целое число \(n\) (\(3 \le n \le 2^{11}\)) — длину перестановки \(p\).

Вторая строка должна содержать \(n\) целых чисел, разделенных пробелами \(p_1\), \(p_2\), \(\ldots\), \(p_n\) (\(0 \le p_i < n\)) — элементы перестановки \(p\).