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

Вам дан массив $$$a$$$ длины $$$n$$$. Необходимо рассчитать массив $$$b$$$ длины $$$n$$$ такой, что $$$b_i = a_i$$$, если для любого $$$j \lt i$$$ верно $$$a_j \ne a_i$$$, и $$$b_i = a_i + 1$$$ в противном случае.

Изучая характеристики устройства одной из нейронных сетей, Марк выделил некоторый массив $$$a$$$, который он получил после преобразования параметров сети. Более того, он убедился, что этот массив некоторым образом связан с эффективностью сети. Однако он не уверен, как данный массив меняется при дальнейшем процессе обучения. Марк предполагает, что в процессе обучения массив может изменяться только $$$1$$$ типом операции. Для проверки он запустил процесс обучения и получил новый массив $$$b$$$. Теперь он просит вас помочь проверить его гипотезу.

Вам дан массив $$$a$$$. Над ним можно выполнить следующую операцию любое количество раз: выбрать элемент массива $$$x$$$ и вместо него вставить 2 элемента величины $$$x + 1$$$ в эту позицию. Длина массива при этом увеличивается на $$$1$$$.

Необходимо определить, возможно ли получить массив $$$b$$$.

Играя в настольный теннис Andrew-13 задумался, возможно ли завершить игру в точности после раунда $$$x$$$.

Обычный настольный теннис идёт, пока один из игроков не наберёт хотя бы 11 очков с преимуществом хотя бы в 2 очка по сравнению со вторым игроком, но игры с такими правилами могут быстро заканчиваться. Поэтому Andrew-13 решил рассмотреть теннис, где игра идёт, пока один из игроков не наберёт хотя бы $$$n$$$ очков с преимуществом хотя бы в $$$k$$$ очков.

Изначально у каждого игрока $$$0$$$ очков. Затем начинаются игровые раунды. Каждый раунд заканчивается победой одного из двух игроков(ничьей не бывает), который получает $$$+1$$$ очко. Как только у одного из игроков есть хотя бы $$$n$$$ очков и при этом у него хотя бы на $$$k$$$ очков больше, чем у соперника, игра заканчивается.

Вам необходимо определить для $$$t$$$ возможных параметров $$$n, k$$$ и $$$x$$$, может ли игра окончиться в точности после раунда $$$x$$$ (раунды нумеруются, начиная с $$$1$$$).

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

После некоторого времени вы разобрались в структуре автомата – в нём есть $$$n$$$ вершин и $$$m$$$ направленных рёбер между ними. На каждом ребре написана буква латинского алфавита, а некоторые вершины являются терминальными. В соответствующем графе могут быть петли и кратные рёбра.

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

Изначально $$$x = 1$$$ – текущее состояние. Далее символы строки рассматриваются по очереди. Если из текущей вершины нет перехода по очередному символу $$$s$$$, то процесс заканчивается, и строка считается неподходящей. Если переходы по символу $$$s$$$ есть, то состояние изменяется на одно из состояний, достижимых из $$$x$$$ по букве $$$s$$$.

Обратите внимание на то, что из одной вершины может быть несколько переходов по букве $$$s$$$, однако чтобы строка считалась подходящей, достаточно, чтобы хотя бы 1 путь заканчивался в терминальной вершине.

Дополнительно пустая строка считается $$$подходящей$$$ вне зависимости от структуры автомата.

Необходимо определить максимальную длину строки, которая является $$$подходящей$$$.

Если длина конечна, то нужно вывести лексикографически минимальную строку максимальной длины.

Для строк одинаковой длины $$$S, T$$$ $$$(S \ne T)$$$ $$$S$$$ называется лексикографически меньше, чем $$$T$$$, если существует $$$i$$$, такое что для $$$j$$$ ($$$1 \le j \lt i$$$) $$$S_{j} = T_j$$$ и $$$S_{i} \lt T_i$$$.

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

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

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

Для того чтобы получить о нём информацию, вы можете делать запросы. В каждом запросе вы можете выбрать множества $$$S, T$$$, которые являются подмножествами {$$$1, 2, \ldots n$$$}. В ответ вы получите количество рёбер, начинающихся в одной из вершин множества $$$S$$$ и заканчивающихся в одной из вершин множества $$$T$$$(учитывая ориентацию рёбер). Множества $$$S$$$ и $$$T$$$ могут пересекаться.

Вы можете задать не более $$$n$$$ запросов. В любой момент вы можете вывести ответ на задачу – индекс вершины, которая является листом, или $$$-1$$$, если в графе нет ни одного листа.

В первой строке вводится число $$$t$$$ ($$$1 \le t \le 100$$$) – количество тестов.

В очередном тесте вводится число $$$n$$$ ($$$1 \le n \le 100$$$) – количество вершин в графе. Гарантируется, что сумма $$$n$$$ по всем тестовым данным не превосходит $$$1000$$$.

Далее ваша программа может выбрать множества $$$S$$$ = {$$$s_1, s_2, \ldots, s_k$$$} и $$$T$$$ = {$$$t_1, t_2, \ldots, t_r$$$} и вывести «? $$$k$$$ $$$s_1$$$ $$$s_2 \ldots s_k$$$ $$$r$$$ $$$t_1$$$ $$$t_2 \ldots t_r$$$». После этого вы получите количество рёбер, начинающихся в одной из вершин множества $$$S$$$ и заканчивающихся в одной из вершин множества $$$T$$$. Обратите внимание, что при выполнении запроса после последнего числа не должно быть лишних пробелов.

Как только программа готова дать ответ, вы можете вывести «! $$$x$$$», где $$$x$$$ равен $$$-1$$$, если листа не существует, или индексу листа в противном случае (индексация начинается с $$$1$$$). Далее программа должна приступить к обработке следующего теста или завершиться, если это был последний тест.

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

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

• fflush(stdout) или cout.flush() в C++;
• sys.stdout.flush() в Python;

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

Есть массив целых ненулевых чисел $$$a_1, a_2, \ldots, a_n$$$, положительное число $$$x$$$ в массиве соответствует $$$x$$$ открывающимся скобкам, а отрицательное – $$$-x$$$ закрывающимся. Например, массив [3, -2] соответствует ((()).

Подотрезок $$$a_l, a_{l+1}, \ldots, a_r$$$, где $$$(l \le r)$$$ называется $$$хорошим$$$, если можно переупорядочить его элементы и получить массив $$$b_1, b_2, \ldots, b_{r-l+1}$$$ такой, что соответствующая ему скобочная последовательность является сбалансированной и при этом среди любых двух подряд идущих элементов массива $$$b$$$ есть хотя бы одно отрицательное число.

Для данного массива $$$a$$$ вам необходимо посчитать число его $$$хороших$$$ подотрезков.

Скобочная последовательность называется сбалансированной, если её можно превратить в правильное математическое выражение, добавив символы + и 1.

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

Игра проходит следующим образом. Изначально у каждого игрока $$$0$$$ очков. Затем начинаются игровые раунды. Каждый раунд заканчивается победой одного из двух игроков(ничьей не бывает). Как только у одного из игроков есть хотя бы $$$n$$$ очков и при этом у него хотя бы на $$$k$$$ очков больше, чем у соперника, игра заканчивается.

Андрей и Саша сыграли между собой много игр. Однако информация о некоторых из них была утеряна. Андрей помнит, что всего было сыграно $$$g$$$ раундов, и из них он выиграл от $$$l$$$ до $$$l+13$$$ раундов. Если он выиграл $$$x$$$ раундов, можно считать, что вероятность победы Андрея в каждом раунде постоянна и равна $$$x/g$$$. Эта вероятность также не меняется по ходу следующих игр.

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

Ответ необходимо вывести по модулю $$$998244353$$$.