Где-то в параллельной вселенной, SDU Open — это новая международная олимпиада для школьников в области информатики. Она призвана привлечь талантливых учащихся из разных стран мира и дать им возможность продемонстрировать свои знания и навыки в соревновании.

Согласно традициям международных олимпиад, в первый год проведения SDU Open медали будут разданы следующим образом:

• Хотя бы $$$1/12$$$ участников должны получать золотые медали;
• Хотя бы $$$1/4$$$ участников должны получать серебряные медали или выше;
• Хотя бы $$$1/2$$$ участников должны получать бронзовые медали или выше.

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

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

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

У вас есть перестановка $$$p$$$ длины $$$n$$$, отсортированная в убывающем порядке. Вы хотите отсортировать эту перестановку в возрастающем порядке. Для этого вы можете выполнять следующую операцию:

• Выбрать два подряд идущих блока одинакогого размера и поменять их местами. Другими словами, вы выбираете два целых числа $$$(s, k)$$$ таких, что $$$1 \le s, k \le n$$$ и $$$s + 2k - 1 \le n$$$ и меняете местами блоки $$$(p_s, \ldots, p_{s+k-1})$$$ и $$$(p_{s+k}, \ldots, p_{s+2k-1})$$$.

Например, если $$$p = (2, 3, 1, 4, 5, 7, 6)$$$ и вы сделаете операцию с парой $$$s = 2$$$ и $$$k=2$$$, то вы получите перестановку $$$p = (2, 4, 5, 3, 1, 7, 6)$$$ поменяв местами подряд идущие блоки $$$(3, 1)$$$ и $$$(4, 5)$$$ длины $$$2$$$.

Отсортируйте $$$p$$$ по возрастанию используя не более $$$n$$$ операций.

Определим серию бинарной строки как максимальную непрерывную подстроку этой строки, состоящей только из одного и того же символа, либо $$$0$$$, либо $$$1$$$. Например, в бинарной строке '110100011001' есть семь серий: '11', '0', '1', '000', '11', '00' и '1'.

Возьмем произвольную бинарную строку $$$S$$$ длины $$$n$$$ и рассмотрим все её серии. Отсортируем все её серии состоящие из нулей в порядке неубывания длины. Аналогично, отсортируем все серии состоящие из единиц. Затем объединим все эти серии сохраняя относительный порядок между блоками из нулей и единиц и получим новую строку $$$S'$$$. Назовем эту новую строку серийным представителем строки $$$S$$$.

Например, сделаем эту процедуру для строки '110100011001' приведенной выше:

• Все серии состоящие из нулей: '0', '000', '00'. Отсортируем по длине и получим '0', '00', '000'.
• Все серии состоящие из единиц: '11', '1', '11', '1'. Отсортируем по длине и получим '1', '1', '11', '11'.
• Объединим полученные серии сохраняя относительный порядок между блоками из нулей и единиц. Получим '1', '0', '1', '00', '11', '000', '11'. Распишем как строку и получим '101001100011'. Эта строка является серийным представителем изначальной строки '110100011001'.

Вам дано одно целое число $$$n$$$. Вашей задачей является посчитать количество бинарных строк $$$S$$$ длины $$$n$$$ таких, что её серийный представитель $$$S'$$$ лексикографически меньше самой строки $$$S$$$ ($$$S' \lt S$$$). Поскольку ответ может быть очень большим, посчитайте его по модулю $$$998\,244\,353$$$.

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

Тима и Батыр играют серию матчей в игре UFC. В игре присутствует $$$n$$$ бойцов, которые пронумерованы в порядке своей силы от $$$1$$$ (самый слабый) до $$$n$$$ (самый сильный).

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

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

Если в какой-то момент серии Батыр выигрывает больше матчей, чем Тима, он объявляет себя более сильным игроком и уходит домой. Однако, если все $$$n$$$ матчей сыграны, и Батыр не ушел домой, то он признает силу Тимы.

Вам, как самому верному фанату Тимы, стало интересно: сколько есть способов выбрать порядок бойцов для игроков так, чтобы Тима утер нос Батыру? Так как ответ может быть очень большим, вычислите его по модулю $$$998\, 244\, 353$$$.

Батыр и Мазен решили пойти в популярное место, где готовят вок и предлагают $$$n$$$ различных добавок. Каждая добавка меняет вкус вока на $$$a_i$$$, который также может быть и отрицательным числом. Вок без никаких добавок имеет вкус $$$0$$$.

Они хотят попробовать все возможные воки, которых всего $$$2^n$$$. Батыр хочет записать в список порядок в котором они будут пробовать все воки. Затем он поделится этим списком с Мазеном. Однако, поскольку родной язык Мазена - арабский, он будет читать этот список справа налево. Это означает, что первый вок в списке Батыра будет последним в списке Мазена и наоборот.

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

Определите, может ли Батыр создать такой список?

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

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

На протяжении последних нескольких дней в джунглях независимо оказывались $$$q$$$ людей без карты и других способов навигации. Вам известно по записям спасателей, что $$$i$$$-й из них начинал свой маршрут у дерева $$$s_i$$$ и блуждал до того, как в первый раз доходил до дерева $$$t_i$$$ где он находил записку от спасателей где был написан способ выхода из джунглей.

Каждый из этих людей блуждал абсолютно случайным образом, смотря на каждом шагу на всевозможные тропинки по которым он может пойти, и равновероятно выбирая любой из них, доходя до другого конца тропинки и заново повторяя этот процесс. Вероятность перемещения с дерева $$$u$$$ на соединенное тропинкой дерево $$$v$$$ была равна $$$\frac{1}{c_u}$$$, где $$$c_u$$$ — общее количество тропинок у дерева $$$u$$$. Каждый из них никогда не сдавался и никогда не оставался у того же самого дерева, постоянно ходя по тропинкам и ища выход.

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

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

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

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

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

Вместо больших простых чисел он решил кодировать свои данные одним массивом положительных целых чисел $$$a_1, \ldots, a_n$$$. Этот массив имеет значение только если он упорядочен в определенном порядке, поэтому Алекс хорошим образом перемешал свой массив.

Алекс знает, что изначальный порядок имел очень особенное свойство: числа $$$(a_i + i)$$$ не были взаимно простыми. Более формально, выполнялось условие $$$\text{НОД}(a_1 + 1, a_2 + 2, \ldots, a_n + n) \neq 1$$$.

Вскоре Алекс заметил, что расшифровать его шифр — далеко не одна из простых задач. У него есть уже перемешанный массив $$$a_1, \ldots, a_n$$$ длины $$$n$$$. Помогите ему восстановить изначальный порядок массива или сообщите Алексу что такого порядка не существует и он где-то ошибся. Если таких порядков может быть несколько, можно вывести любой.

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

У очень известного мобильного оператора SDUcell есть $$$n$$$ радиовышек в городе. В данной задаче город можно представить как двумерную Евклидову плоскость и $$$i$$$-я радиовышка находится на целочисленной координате $$$(x_i, y_i)$$$. Расстояние между двумя точками измеряется Евклидовым расстоянием, то есть длиной кратчайшего отрезка, соединяющего заданные точки.

Активный пользователь данного оператора Марко решил прогуляться по улицам города и поболтать с друзьями во время прогулки. Он уже определился со своим маршрутом и выделил $$$m$$$ точек на карте.

Он начинает свой маршрут в точке $$$(a_1, b_1)$$$. Дальше он будет ходить по прямой линии до точки $$$(a_2, b_2)$$$, оттуда до точки $$$(a_3, b_3)$$$ и так далее. В итоге он закончит свой маршрут в точке $$$(a_m, b_m)$$$.

Особенность его маршрута в том, что улицы в городе расположены в прямоугольном виде. Поскольку Марко всегда гуляет по улицам, каждая часть его маршрута будет либо строго горизонтальной, либо вертикальной. Более формально, для всех $$$1 \le i \le m-1$$$ всегда будет выполняться либо $$$a_i = a_{i+1}$$$, либо $$$b_i = b_{i+1}$$$.

Марко двигается с постоянной скоростью одной единицы в секунду. То есть, пройденное расстояние прямо пропорционально потраченному времени и Марко пройдет $$$d$$$ единиц расстояния за $$$d$$$ секунд.

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

• Обозначим общее количество времени в пути Марко как $$$d$$$. Будем считать, что Марко начал звонок в момент времени $$$0$$$ и завершил его в момент времени $$$d$$$. Для каждого момента времени $$$t$$$ ($$$0 \le t \le d$$$) определим значение $$$f(t)$$$ как расстояние от Марко до ближайшей радиовышки в этот момент.
• Тогда стоимость звонка в тенге будет определяться как площадь под функцией $$$C(t) = f(t)^2$$$ в промежутке $$$[0, d]$$$.

Какую сумму придется заплатить Марко?

Данияр — храбрый рыцарь, сражающийся с $$$n$$$ монстрами, которые расположены в ряд. $$$i$$$-й монстр слева имеет силу $$$a_i$$$.

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

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

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

К сожалению, прямо перед битвой Данияр сломал свой меч. Чтобы решить эту проблему, ему необходимо срочно отправиться к ближайшему кузнецу, чтобы купить новый меч. Однако он не уверен в длине меча, который ему стоит приобрести. Он хочет определить минимальную силу самого сильного монстра, который все еще будет жив, если бы у него был меч длины $$$k$$$ для каждого возможного значения $$$k$$$ ($$$1 \le k \le n$$$).

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

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

Когда организаторы SDU Open нуждались в шеф-поваре, чтобы приготовить стейки для участников конкурса, они знали, что Егор — идеальный человек для этой работы.

В настоящее время в очереди ожидают $$$n$$$ участников, $$$i$$$-й из которых должен съесть хотя бы $$$a_i$$$ стейков, чтобы удовлетворить свой голод и съесть $$$b_i$$$ стейков, чтобы чувствовать себя сытым.

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

Если известно, что Егор сможет приготовить не более $$$k$$$ стейков, какое максимальное количество участников он может насытить?

В Барселоне есть $$$n$$$ различных почтовых индексов $$$a_1, \ldots, a_n$$$. Каждый почтовый индекс — это целое $$$5$$$-значное число (возможно с лидирующими нулями).

За каждый почтовый индекс отвечает ровно один почтовый офис. Все доставки на конкретный почтовый индекс всегда приходят в офис.

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

• Почтовые офисы под номерами $$$i$$$ и $$$j$$$ ($$$1 \le i \lt j \le n$$$) поделятся контактными номерами друг друга только если их почтовые индексы $$$a_i$$$ и $$$a_j$$$ отличаются ровно в $$$k$$$ цифрах.

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

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

Томмасо пока что не знает почтовый индекс своего места жительства. Вам стало интересно: для всех возможных вариантов $$$s$$$ ($$$1 \le s \le n$$$) почтового офиса места жительства Томмасо, про сколько различных почтовых офисов Томмасо сможет разузнать если он начнет с него?

В SDU есть группа из $$$n$$$ студентов бакалавриата, заинтересованных в участии в предстоящих ICPC соревнованиях. Для каждого студента известен его уровень силы, обозначенный одним целым числом $$$a_i$$$.

Также в университете есть $$$m$$$ аналогичных студентов магистратуры, которые заинтересованы в роли тренера. Для каждого из них также известен его уровень силы, обозначенный одним целым числом $$$b_i$$$.

Администрация SDU заинтересована в том, насколько потенциально сбалансированную команду можно собрать с их университета. Для этого нужно сформировать команду из трех студентов бакалавриата $$$i$$$, $$$j$$$ и $$$q$$$ ($$$1 \le i \lt j \lt q \le n$$$). Сила команды будет определена суммой индивидуальных участников команды, а именно — числом $$$a_i + a_j + a_q$$$.

Однако команда не будет полноценно развиваться без тренера. Поэтому было принято решение выбрать одного тренера из студентов магистратуры. Пусть номер выбранного тренера будет $$$k$$$ $$$(1 \leq k \leq m)$$$. Тогда нужно чтобы дополнительно выполнялись следующие условия:

1. Тренер должен быть сильнее команды, чтобы он смог их тренировать. Поэтому должно выполняться условие $$$b_k \gt a_i + a_j + a_q$$$.
2. Тренер не должен быть слишком сильным по сравнению с командой, чтобы тренеру не было скучно учить, а участникам не было слишком сложно тренироваться.

Учитывая вышеописанные ограничения, было принято решение составить подходящую команду так, чтобы разница между силой тренера и силой команды $$$b_k - (a_i + a_j + a_q)$$$ была минимальной. Если возможно составить несколько подходящих команд, можно выбрать любую.

Помогите собрать команду мечты.