Залы всех кинотеатров Берлядии представляют собой прямоугольники в K рядов по K кресел в каждом, причем K — нечетное число. Ряды и места нумеруются с 1 до K. Из соображений безопасности, человек, пришедший в кассу за билетами, не может сам выбрать места. Раньше это делал кассир, а теперь этим будет заниматься специальная программа рассадки. Было выяснено, что подавляющее большинство жителей Берляндии в кинотеатре предпочитают смотреть фильм, поэтому хотят сидеть как можно ближе к центру зала. Кроме того, компания из M человек, желающая посмотреть фильм, хочет непременно занять M последовательных мест в одном ряду. Сформулируем алгоритм, в соответствии с которым программа выдает людям билеты. При поступлении запроса на M мест программа должна определить номер ряда x и отрезок [y_l, y_r] номеров кресел на этом ряду, причем y_r - y_l + 1 = M. Из всех таких возможных вариантов программа должна выдать тот, для которого значение функции суммарной удаленности от центра минимально. Пусть — номер ряда и номер места у самого "центрального" кресла. Тогда значением функции удаленности от центра зала будет . Если вариантов с минимальным значением этой функции несколько, то программа должна выдать тот, что ближе к экрану (т.е. номер ряда x меньше). Если же вновь имеется неоднозначность, следует выдать вариант с минимальным y_l. Если вы еще не догадались, то ваша задача — промоделировать работу программы.

Последовательность целых чисел \(a_1, a_2, \dots, a_k\) называется хорошим массивом, если \(a_1 = k - 1\) и \(a_1 > 0\). Например последовательности \([3, -1, 44, 0], [1, -99]\) — хорошие массивы, а последовательности \([3, 7, 8], [2, 5, 4, 1], [0]\) — нет.

Последовательность целых чисел называется хорошей, если она состоит из положительного количества подряд идущих хороших массивов. Например последовательности \([2, -3, 0, 1, 4]\), \([1, 2, 3, -3, -9, 4]\) — хорошие, а последовательности \([2, -3, 0, 1]\), \([1, 2, 3, -3 -9, 4, 1]\) — нет.

Для заданной последовательности чисел подсчитайте количество её подпоследовательностей, которые являются хорошими последовательностями, по модулю 998244353.

Дан текст, состоящий из \(n\) слов, разделённых пробелами. Между каждой парой соседних слов ровно один пробел. Перед первым словом и после последнего слова нет пробелов. Длина текста — это количество букв и пробелов в нём. \(w_i\) обозначает \(i\)-е слово текста. Все слова состоят только из строчных букв латинского алфавита.

Определим отрезок слов \(w[i..j]\) как последовательность слов \(w_i, w_{i + 1}, \dots, w_j\). Два отрезка слов \(w[i_1 .. j_1]\) и \(w[i_2 .. j_2]\) считаются одинаковыми, если \(j_1 - i_1 = j_2 - i_2\), \(j_1 \ge i_1\), \(j_2 \ge i_2\), и для каждого \(t \in [0, j_1 - i_1]\) \(w_{i_1 + t} = w_{i_2 + t}\). Например, в тексте "to be or not to be" отрезки \(w[1..2]\) и \(w[5..6]\) одинаковы, они соответствуют последовательности слов "to be".

Аббревиация — это замена некоторых слов в тексте их первыми заглавными буквами. Чтобы использовать аббревиацию, вы должны выбрать хотя бы два непересекающихся одинаковых отрезка слов и заменить каждый из выбранных отрезков на строку, состоящую из первых букв этих слов (буквы в новой строке являются заглавными). К примеру, в тексте "a ab a a b ab a a b c" можно заменить отрезки слов \(w[2..4]\) и \(w[6..8]\) аббревиацией "AAA" и получить текст "a AAA b AAA b c", или заменить \(w[2..5]\) и \(w[6..9]\) на аббревиацию "AAAB" и получить текст "a AAAB AAAB c".

Чему равна минимальная длина текста после использования не более чем одной аббревиации?

Поликарп очень любит числа, которые делятся на \(3\).

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

Например, если исходное число \(s=3121\), то Поликарп может разрезать его на три части двумя разрезами \(3|1|21\). В результате он получит два числа, которые делятся на \(3\).

Поликарп может провести произвольное количество разрезов, каждый разрез проводится между парой соседних цифр. Числа, которые получатся в итоге не могут содержать лишних лидирующих нулей (то есть число может начинаться с 0 тогда и только тогда, когда это число в точности один символ '0'). Например, 007, 01 и 00099 не являются корректными числами, а 90, 0 и 10001 — являются.

Какое наибольшее количество делящихся на три чисел он сможет получить?

В упрощённой версии игры мини-метро есть только одна линия метро, на которой поезда ходят всегда в одну сторону. На линии расположено \(n\) станций, на \(i\)-й станции в начале игры ждут поезда \(a_i\) людей. Игра начинается в начале \(0\)-го часа. В конце каждого часа (за пару минут до конца часа) на станцию \(i\) мгновенно прибывают ещё \(b_i\) людей. Если в какой-то момент число людей на \(i\)-й станции превышает \(c_i\), то вы проиграли.

У игрока в распоряжении есть несколько поездов, которые он может распределить по часам. Вместимость каждого поезда — \(k\) пассажиров. В середине назначенного ему часа поезд моментально проходит с \(1\)-й по \(n\)-ю станции, забирая с каждой станции столько человек, сколько ещё может вместить. То есть поезд не может забрать людей со станции \(i\), если ещё есть люди на станции \(i-1\).

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

Игрок хочет продержаться в игре \(t\) часов. Определите, какое минимальное число поездов ему для этого потребуется.

Геральд находится в старинном замке из n залов, соединенных n - 1 переходами. Из любого зала можно добраться до любого другого единственным способом, то есть граф представляет собой дерево. Изначально, в момент времени 0, Геральд находится в зале номер 1. Также в некотором другом зале этого замка находится клад, который Геральд хочет найти. Где именно находится клад неизвестно, он может быть с одинаковой вероятностью в любом из остальных n - 1 залов. Узнать о местонахождении клада Геральд может только тогда, когда придет непосредственно в тот зал. Тогда Геральд сразу же видит клад, и этот момент считается моментом достижения его цели.

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

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

Более формально, если клад окажется во втором зале, то Геральд найдет его в тот момент, когда первый раз окажется во втором зале — пусть это будет в момент t₂. Если в третьем, то Геральд найдет его тогда, когда первый раз окажется в третьем зале. Пусть это произойдет в момент времени t₃. И так далее. Таким образом, среднее время нахождения клада окажется равным .

Добро пожаловать в город Иннополис. Весь год бедные жители Иннополиса страдают от постоянного строительства.

Из окна вашей комнаты, вы можете увидеть последовательность из n холмов, где высота i-го из них равна a_i. Администрация города Иннополис хочет построить несколько домов на этих холмах. При этом для красоты города было принято решение, что дом может быть построен только на холме, который строго выше соседних холмов (если таковые есть). Например, если последовательность высот это 5, 4, 6, 2, то в этом случае дом может быть построен только на холмах с высотой 5 и 6.

У администрации Иннополиса есть экскаватор, который может уменьшить высоту любого холма на единицу за один час. Экскаватор может работать только над одним холмом одновременно. Разрешено уменьшать высоту холмов до нуля, или даже до отрицательных значений. Увеличение высоты любого холма невозможно. Администрация города хочет построить k домов, поэтому должно быть хотя бы k холмов, которые соотвествуют условию, описанному выше. Какое минимальное количество времени нужно, чтобы осуществить план администрации?

Однако, конкретная величина k до сих пор не определена. Вам предлагается посчитать нужную величину для всех возможных k в отрезке . Здесь обозначает n делённое на 2, округлённое вверх.

Звезда — это фигура на клетчатом поле следующего вида: символ звездочка '*' в центре фигуры и четыре луча (влево, вправо, вверх и вниз) одинаковой положительной длины. Размером звезды является длина ее лучей. Размер звезды должен быть строго положительным (то есть лучи длины \(0\) недопустимы).

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

Левая фигура — звезда размера \(1\), средняя фигура — звезда размера \(2\) и правая фигура — звезда размера \(3\).

Задано прямоугольное поле размера \(n \times m\), состоящее из звездочек '*' и точек '.'. Строки пронумерованы от \(1\) до \(n\), столбцы пронумерованы от \(1\) до \(m\). Ваша задача — нарисовать это поле при помощи любого количества звезд или понять, что это невозможно сделать. Звезды могут пересекаться, вкладываться и даже совпадать друг с другом. Количество звезд в ответе не может превышать \(n \cdot m\). Каждая из звезд должна находиться строго внутри поля. Вы можете использовать звёзды как одинаковых так и различных размеров.

В этой задаче нет необходимости минимизировать количество звезд. Необходимо найти любой способ нарисовать заданное поле при помощи не более, чем \(n \cdot m\) звезд.

Задана скобочная последовательность \(s\) (не обязательно правильная). Скобочная последовательность — это строка, состоящая только из символов '(' и ')'.

Правильная скобочная последовательность — это скобочная последовательность, которая может быть преобразована в корректное арифметическое выражение при помощи вставки символов '1' и '+' между изначальными символами последовательности. Например, скобочные последовательности «()()» и «(())» являются правильными (полученные выражения выглядят следующим образом: «(1)+(1)» и «((1+1)+1)»), а «)(», «(» и «)» — нет.

Ваша задача — посчитать количество правильных скобочных последовательностей длины \(2n\), содержащих заданную скобочную последовательность \(s\) как подстроку (последовательность подряд идущих символов) по модулю \(10^9+7\) (\(1000000007\)).

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

Время пути между некоторыми городами \(v\) и \(u\) — это суммарная длина дорог на кратчайшем пути из \(v\) в \(u\).

Два наиболее важных города Берляндии имеют номера \(1\) и \(n\).

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

Новая дорога может быть построена только между такими городами \(v\) и \(u\), что \(v \neq u\) и \(v\) и \(u\) еще не соединены никакой дорогой.

Они создали планы \(m\) возможных проектов. Каждый проект — это просто длина \(x\) новой дороги.

Поликарп работает главным аналитиком Министерства Транспорта Берляндии, разбираться с этими \(m\) проектами — его задача. Для \(i\)-го проекта он должен выбрать некоторые города \(v\) и \(u\) и построить новую дорогу длины \(x_i\) между ними так, чтобы время пути между самыми важными городами было максимально возможным.

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

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

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

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

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

Ваша задача — подсчитать количество подходящих раскрасок доски заданного размера.

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

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

Вы хотите собрать контест, состоящий из некоторых задач из заданного набора. Другими словами, контест, который вы хотите собрать, должен быть подмножеством задач (не обязательно подряд идущих) из заданного набора. Должно быть соблюдено только одно условие: для каждой задачи, кроме самой сложной (задачи с максимальной сложностью) задачи контеста, должна быть задача со сложностью больше сложности этой задачи, но не больше, чем удвоенная сложность этой задачи. Другими словами, пусть \(a_{i_1}, a_{i_2}, \dots, a_{i_p}\) — сложности задач в собранном контесте в возрастающем порядке. Тогда для каждого \(j\) от \(1\) до \(p-1\) должно выполняться \(a_{i_{j + 1}} \le a_{i_j} \cdot 2\). Это означает, что контест, состоящий из одной задачи всегда является корректным.

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

У Васи есть последовательность \(a\) состоящая из \(n\) целых чисел \(a_1, a_2, \dots, a_n\). За одну операцию Вася может выбрать число из последовательности и поменять местами два любых бита в его двоичной записи. Например из числа \(6\) \((\dots 00000000110_2)\) Вася может получить числа \(3\) \((\dots 00000000011_2)\), \(12\) \((\dots 000000001100_2)\), \(1026\) \((\dots 10000000010_2)\) и так далее. Вася может применять эту операцию любое количество раз (возможно, ни разу) к любому из заданных чисел.

Вася считает последовательность чисел хорошей, если, применяя к ней описанную выше операцию, он может получить последовательность, побитовое исключающее ИЛИ всех элементов которой равно \(0\).

Для заданной последовательности \(a_1, a_2, \ldots, a_n\) Вася хочет знать количество пар целых чисел \((l, r)\) таких, что \(1 \le l \le r \le n\) и последовательность \(a_l, a_{l + 1}, \dots, a_r\) является хорошей.

У вас есть набор из \(n\) гирек. Вам известно, что они весят \(a_1\), \(a_2\), ..., \(a_n\) граммов, но вы не знаете, какая гирька сколько весит: для вас они неотличимы друг от друга.

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

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

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

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

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

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

Little C очень любит число «3». Он любит все, что с ним связано.

В данный момент его заинтересовала следующая задача:

Даны два массива из \(2^n\) целых чисел: \(a_0,a_1,...,a_{2^n-1}\) и \(b_0,b_1,...,b_{2^n-1}\).

Задача состоит в том, чтобы для каждого \(i (0 \leq i \leq 2^n-1)\), вычислить \(c_i=\sum a_j \cdot b_k\) (\(j|k=i\) и \(j\&k=0\), где "\(|\)" обозначает побитовую операцию ИЛИ и "\(\&\)" обозначает побитовую операцию И).

Это замечательно, что можно доказать, что существует ровно \(3^n\) троек \((i,j,k)\), для которых \(j|k=i\), \(j\&k=0\) и \(0 \leq i,j,k \leq 2^n-1\). Поэтому Little C хочет решить эту отличную задачу (потому что она тесно связана с числом \(3\)) .

Помогите ему вычислить все \(c_i\). Little C очень любит число \(3\), поэтому он лишь хочет знать все \(c_i \& 3\).

Вам даны две бинарные строки \(a\) и \(b\) равной длины. Вы можете производить над строкой \(a\) следующие операции:

• Поменять два бита на позициях \(i\) и \(j\) соответственно (\(1 \le i, j \le n\)), стоимость этой операции составляет \(|i - j|\), то есть модуль разницы \(i\) и \(j\).
• Выбрать произвольную позицию \(i\) (\(1 \le i \le n\)) и инвертировать (заменить \(0\) на \(1\) или \(1\) на \(0\)) значение бита на этой позиции. Стоимость этой операции равна \(1\)

Найдите минимальную стоимость, которую нужно потратить, чтобы сделать строку \(a\) равной строке \(b\). Менять строку \(b\) не разрешается.

Вам даны \(n\) блоков, каждый из которых выглядит как [color\(_1\)|value|color\(_2\)], при чём блок можно также перевернуть, чтобы получить [color\(_2\)|value|color\(_1\)].

Назовём последовательность блоков корректной, если касающиеся концы блоков совпадают по цветам. Например, последовательность из трёх блоков A, B и C является корректной, если левый цвет B совпадает с правым цветом A и правый цвет B совпадает с левым цветом C.

Ценность последовательности равна сумме ценностей (value) отдельных блоков в ней.

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

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

Вам дано дерево на \(n\) вершинах. Для каждого \(k\) от \(1\) до \(n\) включительно найдите максимально возможную мощность \(k\)-допустимого множества простых путей.

Вам задана зеркальная изнутри труба в виде двух несовпадающих прямых, параллельных оси \(Ox\). На каждой из прямых отмечены некоторые целочисленные точки — позиции сенсоров на стенках трубы.

Вы собираетесь провести эксперимент с этой трубой и лазерным лучом. Для этого надо выбрать две целочисленные точки \(A\) и \(B\) на первой и второй прямой соответственно (координаты точек могут быть отрицательные): точка \(A\) будет отвечать за позицию лазера, а точка \(B\) — за направление лазерного луча. Лазерный луч представляет собой луч, стартующий в \(A\) и направленный в \(B\), который отражается от стенок трубы (независимо от того, есть в данной точке сенсор или нет). Сенсор регистрирует луч, если он попадает точно в позицию сенсора.

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

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

У Васи есть волшебная матрица \(a\) размера \(n \times m\). Строки матрицы нумеруются от \(1\) до \(n\) сверху вниз, столбцы матрицы нумеруются от \(1\) до \(m\) слева направо. Обозначим как \(a_{ij}\) элемент, находящийся на пересечении \(i\)-й строки и \(j\)-го столбца.

Также у Васи есть фишка. Изначально фишка находится на пересечении \(r\)-й строки и \(c\)-го столбца (то есть в ячейке со значением \(a_{rc}\)). Вася выполняет следующую процедуру до тех пор, пока это возможно: среди всех ячеек матрицы, в которых значение меньше, чем в ячейке, содержащей сейчас фишку, Вася случайно и равновероятно выбирает одну ячейку и перемещает свою фишку туда.

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

Евклидово расстояние между ячейками матрицы \((i_1, j_1)\) и \((i_2, j_2)\) равно \(\sqrt{(i_1-i_2)^2 + (j_1-j_2)^2}\).

Определите математическое ожидание очков, которые наберет Вася.

Можно показать, что ответ может быть выражен как \(\frac{P}{Q}\), где \(P\) и \(Q\) — взаимно простые целые числа, а \(Q \not\equiv 0~(mod ~ 998244353)\). Выведите значение \(P \cdot Q^{-1}\) по модулю \(998244353\).

Есть \(n\) точек на плоскости. Многоугольник, сформированный этими \(n\) точками, строго выпуклый, то есть многоугольник выпуклый и нет трех коллинеарных точек (то есть лежащих на одной прямой). Точки пронумерованы от \(1\) до \(n\) по часовой стрелке.

Определим расстояние между двумя точками \(p_1 = (x_1, y_1)\) и \(p_2 = (x_2, y_2)\) как их манхэттенское расстояние: \(\)d(p_1, p_2) = |x_1 - x_2| + |y_1 - y_2|.\(\)

Более того, определим периметр многоугольника как сумму манхэттенских расстояний между всеми соседними парами точек на нем; если точки на многоугольнике упорядочены как \(p_1, p_2, \ldots, p_k\) \((k \geq 3)\), тогда периметр многоугольника равен \(d(p_1, p_2) + d(p_2, p_3) + \ldots + d(p_k, p_1)\).

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

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

В многоугольнике, который изображен посередине, последовательность точек (\(p_1, p_3, p_2, p_4\)) неправильная потому, что многоугольник самопересекается. Правый многоугольник (ребра которого напоминают Манхэттенское расстояние) имеет такую же последовательность и не самопересекается, но мы рассматриваем ребра как прямые отрезки. Правильный способ нарисовать этот многоугольник — это использовать последовательность (\(p_1, p_2, p_3, p_4\)), пример которого можно увидеть на левом рисунке.

Вычислите \(f(3), f(4), \ldots, f(n)\). Другими словами, найдите максимально возможный периметр для каждого количества точек (то есть от \(3\) до \(n\)).

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

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

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

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

Дан список целых чисел \(a_1, a_2, \ldots, a_n\) и \(s\) его подотрезков \([l_j; r_j]\) (где \(1 \le l_j \le r_j \le n\)).

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

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

Поликарп, друг Аркадия, готовится к олимпиаде по программированию и решил написать контест. Контест состоит из \(n\) задач и длится \(T\) минут. Каждая из задач задаётся двумя целыми положительными числами \(a_i\) и \(p_i\) — её сложность и количество баллов за её решение

Опыт Поликарпа подсказывает, что его навык характеризуется положительным вещественным числом \(s\), причем изначально \(s=1.0\). Для решения \(i\)-й задачи Поликарпу требуется \(a_i/s\) минут.

Поликарп очень любит смотреть сериалы, поэтому перед решением каждой из задач он обязательно будет смотреть одну серию. За время просмотра серии его навык уменьшается на \(10\%\), то есть навык \(s\) уменьшается до \(0.9s\). Каждая серия имеет продолжительность \(10\) минут. Приняв решение работать над задачей, Поликарп обязательно сначала смотрит серию, а затем решает без перерывов задачу в течение \(a_i/s\) минут, где \(s\) — его текущий навык. При вычислении \(a_i/s\) округление не используется, просто производится деление целого числа \(a_i\) на вещественное число \(s\).

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

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

Вам дано корневое дерево на \(n\) вершинах, его корень имеет номер \(1\). В \(i\)-й вершине записано число \(w_i\). Разбейте его на минимальное число таких вертикальных путей, что сумма чисел \(w_i\) в вершинах пути не превосходит \(S\), а количество вершин в пути не превосходит \(L\). Каждая вершина должна принадлежать ровно одному пути.

Вертикальным путём называется последовательность вершин \(v_1, v_2, \ldots, v_k\), где \(v_i\) (\(i \ge 2\)) — непосредственный предок \(v_{i - 1}\) в дереве.

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

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

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

Сергей Семёнович решил добавить в схему новые перегоны. А именно, он дорисовал перегон между станциями \(u\) и \(v\), если эти станции не были соединены перегоном напрямую, но у них была общая станция-сосед, то есть существовала такая станция \(w\), что в оригинальной схеме присутствовал перегон между \(u\) и \(w\) и перегон между \(w\) и \(v\). Вам поставлена задача вычислить сумму попарных расстояний между всеми парами станций в получившейся схеме метрополитена.

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

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

Массив \(b_1, b_2, \ldots, b_k\) называется хорошим если он не пуст и для каждого \(i\) (\(1 \le i \le k\)) \(b_i\) делится на \(i\).

Посчитайте количество хороших подпоследовательностей \(a\) по модулю \(10^9 + 7\). Две подпоследовательности считаются различными, если множества индексов входящих в них чисел различны, то есть значения элементов не учитываются при сравнении подпоследовательностей. В частности, у массива \(a\) есть ровно \(2^n - 1\) различных подпоследовательностей (не считая пустую).

Вы наткнулись на новый вид шахматной головоломки. Доска, на которой вы играете, не обязательно \(8 \times 8\), но обязательно \(N \times N\). На каждой клетке записано некоторое число от \(1\) до \(N^2\), и все числа попарно различны. В \(j\)-й клетке \(i\)-й строки записано число \(A_{ij}\).

У вас в распоряжении только три фигуры: конь, слон и ладья. Вначале вы выставляете одну из фигур в клетку с номером \(1\) (вы сами выбираете какую). Далее вы хотите добраться до клетки с номером \(2\) (возможно, проходя через некоторые другие клетки в процессе), далее — до клетки \(3\) и так далее, пока не достигнете клетки \(N^2\). За один шаг вы можете либо сделать один валидный ход текущей фигурой, либо заменить фигуру на другую в вашем распоряжении. Каждая клетка может быть посещена любое количество раз.

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

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

Найдите путь, отвечающий всем условиям.

Максим ходит по декартовой плоскости. Он начинает в точке \((0, 0)\) и за один ход он может перейти в любую из четырех соседних точек (влево, вправо, вверх, вниз). Например, если сейчас Максим находится в точке \((0, 0)\), то за один ход он может пойти в точки:

• \((1, 0)\);
• \((0, 1)\);
• \((-1, 0)\);
• \((0, -1)\).

Также на плоскости есть \(n\) различных ключевых точек. \(i\)-я точка равна \(p_i = (x_i, y_i)\). Гарантируется, что \(0 \le x_i\) и \(0 \le y_i\) и нет ключевой точки \((0, 0)\).

Назовем точками первого уровня такие точки, что \(max(x_i, y_i) = 1\), точками второго уровня такие точки, что \(max(x_i, y_i) = 2\) и так далее. Максим хочет посетить все ключевые точки. Но он не хочет посещать точки уровня \(i + 1\) пока не посетит все точки уровня \(i\). Он начинает посещать точки, начиная с минимального уровня точек из заданного множества.

Пусть расстояние между точками \((x_1, y_1)\) и \((x_2, y_2)\) равно \(|x_1 - x_2| + |y_1 - y_2|\) где \(|v|\) равно абсолютной величине \(v\).

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

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

Ваня играет в компьютерную игру. В ней есть \(n\) квестов. Каждый из квестов можно один раз улучшить, после этого награда за его выполнение увеличится. У каждого квеста есть \(3\) характеристики: \(a_{i}\), \(b_{i}\), \(p_{i}\). Это награда за выполнение квеста до улучшения, награда за выполнение квеста после его улучшения (\(a_{i} < b_{i}\)) и вероятность успешно выполнить этот квест.

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

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

Мистер Вафа учится в German University in Cairo (GUC) и любит играть в баскетбол. Он был приятно удивлен, когда узнал, что GUC планирует принять участие в Ежегодном Соревновании по Баскетболу (Annual Basketball Competition, ABC).

Для соревнования будет собрана команда из n игроков — студентов GUC. Игроки будут случайным образом выбраны среди студентов играющих в баскетбол. Однако, в команде могут быть игроки с разных факультетов. Всего в GUC m факультетов, пронумерованных числами от 1 до m. Мистер Вафа учится на факультете номер h. Для каждого факультета i Мистер Вафа знает число s_i — сколько студентов с него играют в баскетбол, и соответственно могут оказаться членами команды GUC.

Благодаря своим паранормальным способностям, Мистер Вафа знает, что он точно попадет в команду GUC. Теперь он хочет вычислить вероятность того, что вместе с ним в команде окажется хотя бы один студент с его факультета. Так как он очень не любит вычисления с дробными числами, эта задача поручается вам.

Учтите, что все составы команды, в которых есть Мистер Вафа, могут быть выбраны с равной вероятностью. Считайте, что все студенты отличаются друг от друга.

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

В случае Египта известно c условий, налагаемых на повторяемость преступлений. Каждое ограничение представляет собой тип преступления t_i и его разрешенную кратность m_i. Если количество раз, которое Зиад совершил преступление типа t_i кратно m_i, то он не будет наказан за преступления этого типа. Некоторые типы преступлений могут быть перечислены более одного раза. В этом случае достаточно удовлетворить одному из ограничений для этого типа преступления, чтобы не быть наказанным за него. Естественно, если Зиад не совершил ни одного преступления некоторого типа, то он не будет наказан за преступления этого типа.

Обладая вышеприведенной информацией, Зиад интересуется, сколькими способами можно совершить в Египте ровно n преступлений и остаться безнаказанным?

Порядок совершения преступлений имеет значение. Более формально, два способа, последовательности w1 и w2, считаются одинаковыми, если w1_i = w2_i, для любого 1 ≤ i ≤ n.

Polycarp is an introvert person. In fact he is so much of an introvert that he plays "Monsters and Potions" board game alone. The board of the game is a row of \(n\) cells. The cells are numbered from \(1\) to \(n\) from left to right. There are three types of cells: a cell containing a single monster, a cell containing a single potion or a blank cell (it contains neither a monster nor a potion).

Polycarp has \(m\) tokens representing heroes fighting monsters, which are initially located in the blank cells \(s_1, s_2, \dots, s_m\). Polycarp's task is to choose a single cell (rally point) and one by one move all the heroes into this cell. A rally point can be a cell of any of three types.

After Policarp selects a rally point, he picks a hero and orders him to move directly to the point. Once that hero reaches the point, Polycarp picks another hero and orders him also to go to the point. And so forth, until all the heroes reach the rally point cell. While going to the point, a hero can not deviate from the direct route or take a step back. A hero just moves cell by cell in the direction of the point until he reaches it. It is possible that multiple heroes are simultaneously in the same cell.

Initially the \(i\)-th hero has \(h_i\) hit points (HP). Monsters also have HP, different monsters might have different HP. And potions also have HP, different potions might have different HP.

If a hero steps into a cell which is blank (i.e. doesn't contain a monster/potion), hero's HP does not change.

If a hero steps into a cell containing a monster, then the hero and the monster fight. If monster's HP is strictly higher than hero's HP, then the monster wins and Polycarp loses the whole game. If hero's HP is greater or equal to monster's HP, then the hero wins and monster's HP is subtracted from hero's HP. I.e. the hero survives if his HP drops to zero, but dies (and Polycarp looses) if his HP becomes negative due to a fight. If a hero wins a fight with a monster, then the monster disappears, and the cell becomes blank.

If a hero steps into a cell containing a potion, then the hero drinks the potion immediately. As a result, potion's HP is added to hero's HP, the potion disappears, and the cell becomes blank.

Obviously, Polycarp wants to win the game. It means that he must choose such rally point and the order in which heroes move, that every hero reaches the rally point and survives. I.e. Polycarp loses if a hero reaches rally point but is killed by a monster at the same time. Polycarp can use any of \(n\) cells as a rally point — initially it can contain a monster, a potion, or be a blank cell with or without a hero in it.

Help Polycarp write a program to choose a rally point and the order in which heroes move.

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

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

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

Вова уже нарисовал все таблицы и выписал все формулы. Более того, он уже продумал, что отчет будет состоять ровно из \(n\) страниц, и на \(i\)-й страницу будет \(x_i\) таблиц и \(y_i\) формул. Страницы пронумерованы от \(1\) до \(n\).

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

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

Обратите внимание, что счетчик не сбрасывается в начале новой страницы. Например, если страница заканчивается \(3\) таблицами и следующая страница начинается с \(5\) таблиц, то они учитываются, как \(8\) таблиц подряд.

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

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

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

Вова хочет репостнуть ровно \(x\) картинок так, что будут выполнены следующие условия:

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

К примеру, если \(k=1\), Вова хочет репостнуть все картинки. Если \(k=2\), Вове не обязательно репостить все картинки, но для каждой пары соседних картинок хотя бы одна должна быть репостнута.

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

Вам задан массив \(a\) длины \(n\). Вы можете выбрать один отрезок \([l, r]\) (\(1 \le l \le r \le n\)) и целое число \(k\) (положительное, отрицательное или ноль) и изменить \(a_l, a_{l + 1}, \dots, a_r\) на \(k\) каждое (другими словами, \(a_i := a_i + k\) для каждого \(l \le i \le r\)).

Какое максимально возможное количество элементов со значением \(c\) может быть получено после одной такой операции?

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

В \(i\)-м городе стоит бензоколонка, в которой по странным законам Древесной страны можно купить не более \(w_i\) литров бензина. Можно считать, что у Орехуса бесконечное количество денег. У каждой дороги есть длина, и как только Орехус проезжает по ней, количество бензина уменьшается на длину дороги. Конечно, Орехус не сможет поехать по пути, на одной из дорог которого ему не хватит бензина. Он может купить в бензин в любом городе, в котором он был, в том числе в первом и последнем.

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

Орехус нашел строку \(s\), состоящую из латинских букв нижнего регистра. Орехус любознательный парень, поэтому ему стал интересен следующий вопрос: сколько существует строго возрастающих последовательностей \(p_1, p_2, \ldots, p_k\) таких, что:

1. Для каждого \(i\) (\(1 \leq i \leq k\)), \(s_{p_i} =\) 'a'.
2. Для каждого \(i\) (\(1 \leq i < k\)), существует \(j\), что \(p_i < j < p_{i + 1}\) и \(s_j =\) 'b'.

Удовлетворите любопытство Орехуса, или он расстроится.

Это число должно быть посчитано по модулю \(10^9 + 7\).

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

\(\)\frac{\sum\limits_{u \in s} a_u}{k}\(\)

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

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

Пусть \(n\) — целое число. Рассмотрим все перестановки целых чисел от \(1\) до \(n\) в лексикографическом порядке. Объедините их в одну большую последовательность \(p\). Например, если \(n = 3\), то \(p = [1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 2, 1]\). Длина этой последовательности будет \(n \cdot n!\).

Пусть \(1 \leq i \leq j \leq n \cdot n!\) — пара индексов. Мы называем последовательность \((p_i, p_{i+1}, \dots, p_{j-1}, p_j)\) подотрезком \(p\). Его длина определяется как количество элементов, то есть \(j - i + 1\). Его сумма определяется как сумма всех его элементов, то есть \(\sum_{k=i}^j p_k\).

Дано \(n\). Найдите количество подотрезков \(p\) длины \(n\), имеющих сумму \(\frac{n(n+1)}{2}\). Поскольку это число может быть большим, выведите его по модулю \(998244353\) (простое число).

У Васи есть массив, состоящий из \(n\) чисел, а также два числа \(k\) и \(len\). Все числа массива либо лежат в отрезке от \(1\) до \(k\) (включительно), либо равны \(-1\). Массив называется хорошим, если в нем нет подотрезка длины \(len\) или более, состоящего из одинаковых чисел.

Сообщите Васе количество способов заменить все \(-1\) на числа от \(1\) до \(k\) (включительно) так, чтобы получившийся массив был хорошим. Так как количество хороших массивов может быть достаточно большим, выведите его по модулю \(998244353\).

Хасан любит различные игры, и недавно его заинтересовала игра под названием Супер-Бомбардир. В этой игре (которая довольно похожа на футбол) \(p\) игроков бьют пенальти. Победитель — это тот игрок, который забил наибольшее число голов. В случае ничьи, один из игроков, забивших наибольшее число голов, объявляется победителем равновероятно.

Игроки только закончили матч, и теперь ожидают результата. Однако закралась небольшая проблема! Судьи потеряли таблицу с счетом всех игроков! К счастью, до потери они успели посчитать сумму забитых голов, а также для каждого игрока они запомнили нижнюю границу на количество забитых им голов. Однако информация об этих границах конфиденциальна, поэтому Хасан смог узнать только свою нижнюю границу.

Согласно предоставленной информации, он знает, что его счет не меньше \(r\), а сумма счета всех игроков — \(s\).

Поэтому финальное состояние игры может быть записано в виде последовательности \(p\) целых чисел \(a_1, a_2, \dots, a_p\) (\(0 \le a_i\)) — счет игроков. Хасан — игрок номер \(1\), поэтому \(a_1 \ge r\). К тому же \(a_1 + a_2 + \dots + a_p = s\). Два состояния считаются различными, если существует такая позиция \(i\), что значение \(a_i\) различается в этих двух состояниях.

Еще раз, Хасан не знает точного счета игроков (он не знает и свой точный счет). Поэтому он считает, что вероятность получить любое финальное состояние игры одинакова.

Помогите Хасану найти вероятность его победы.

Можно показать, что она может быть представлена в форме \(\frac{P}{Q}\), где \(P\) и \(Q\) — неотрицательные целые числа и \(Q \ne 0\), \(P \le Q\). Сообщите значение \(P \cdot Q^{-1} \pmod {998244353}\).

Все автобусные билеты в Берляндии пронумерованы. Номер каждого билета состоит из \(n\) цифр (\(n\) четно). При этом в номерах билетов могут быть использованы только \(k\) цифр \(d_1, d_2, \dots, d_k\). Допустимо, что номера билетов Берляндии содержат один или более лидирующих нулей, если \(0\) может использоваться в номерах билетов. Например, если \(n = 4\) и в билетах можно использовать две цифры \(0\) и \(4\), то номера \(0000\), \(4004\), \(4440\) могут быть номерами билетов в Берляндии, а номера \(0002\), \(00\), \(44443\) — нет.

Билет в Берляндии считается счастливым, если сумма первых \(n / 2\) цифр равна сумме последних \(n / 2\) цифр.

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

У Makoto есть большая доска, на которой изначально написано целое положительное число \(n\). После этого он ровно \(k\) раз проделает следующую операцию:

Предположим, что число, записанное сейчас на доске, равно \(v\). Тогда он выберет случайным образом один из делителей \(v\) (включая \(1\) и \(v\)) и заменит \(v\) на этот делитель. Так как Makoto использует свой известный генератор случайных чисел (rng) и число \(58\) как сид этого генератора, то все делители имеют одинаковую вероятность выбора.

Makoto интересуется, чему равно математическое ожидание числа, записанного на доске после всех \(k\) операций.

Можно показать, что это число можно представить как \(\frac{P}{Q}\), где \(P\) и \(Q\) взаимно просты и \(Q \not\equiv 0 \pmod{10^9+7}\). Выведите значение \(P \cdot Q^{-1}\) по модулю \(10^9+7\).

Последовательность Туе-Морса-Радецки-Матеуша (Туорса-Радевуша, для краткости) это бесконечная последовательность, получающаяся из конечной последовательности \(\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})\). Так как обе последовательности очень большие, то ответить на вопрос, используя только бумагу и ручку, оказалось затруднительно. Не могли бы вы ему помочь?

Задан простой неориентированный граф. Выведите число простых циклов в нем. Цикл называется простым если не содержит повторяющихся вершин и ребер (т.е. каждая вершина и ребро содержатся в нем не более 1 раза).

Дано дерево из \(n\) вершин. На каждой вершине дерева записано число; на \(i\)-й вершине записано число \(a_i\).

Определим функцию \(g(x, y)\) как наибольший общий делитель всех чисел, записанных на вершинах на простом пути от вершины \(x\) до вершины \(y\) (включая эти две вершины). Также определим \(dist(x, y)\) как количество вершин на простом пути между \(x\) и \(y\), включая концы пути. \(dist(x, x) = 1\) для каждой вершины \(x\).

Посчитайте максимальное значение \(dist(x, y)\) по всем таким парам вершин, что \(g(x, y) > 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\)-приемлемый обход.

У Аюба был массив целых чисел \(a\) длины \(n\) и у этого массива было два необычных свойства:

• Все целые числа в этом массиве были от \(l\) до \(r\) (включительно).
• Сумма всех элементов в массиве делилась на \(3\).

К сожалению, Аюб потерял свой массив, но он помнит размер массива \(n\), а также числа \(l\) и \(r\), так что он попросил вас посчитать количество способов восстановить массив по этим данным.

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

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

Опишем задачу математически. Рассмотрим ось времени с момента \(1\) до момента \(n\). \(i\)-й красный конверт будет доступен с момента времени \(s_i\) до \(t_i\) включительно, он будет содержать \(w_i\) монет. Если Боб хочет забрать из \(i\)-го конверта монеты, то он может это сделать только в целочисленный момент времени между \(s_i\) и \(t_i\) включительно, а после этого он не сможет собирать монеты из других конвертов до времени \(d_i\) включительно. Выполняется \(s_i \leq t_i \leq d_i\).

Боб жадный, поэтому он жадно собирает монеты: в каждый момент времени \(x\) он собирает монеты из доступного конверта с максимальным количеством монет. Если есть несколько доступных конвертов с одинаковым максимальным количеством монет, Боб выберет конверт, параметр \(d\) которого максимальный. Если все еще есть несколько вариантов, Боб выберет один из них случайным образом.

Все было бы хорошо, но Алиса — дочь Боба — не хочет, чтобы ее отец собрал слишком много монет. Она может отвлечь Боба не более чем \(m\) раз, каждый раз — в один целочисленный момент времени. Если Алиса решает отвлечь Боба в момент времени \(x\), он не сможет ничего делать в момент времени \(x\) и продолжит свою обычную стратегию в момент времени \(x + 1\) (включительно), что приведет к тому, что он может пропустить некоторые красные конверты.

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