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

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

Это сейчас все цирки в Берляндии имеют круглую арену диаметром 13 метров, а в древности все было совсем иначе.

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

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

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

Эхсан обожает геометрию! Больше всего ему нравится вращать точки!

Если дана точка на плоскости, Эхсан любит вращать её на k градусов (против часовой стрелки) вокруг начала координат. Каков результат такого вращения?

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

Математики Берляндского Государственного Университета (БГУ) придумали специальную оценку, которую назвали интенсивностью температуры. Эта оценка считается следующим образом:

Предположим, что мы хотим проанализировать отрезок из \(n\) подряд идущих дней. Мы измерили температуры в каждый из этих \(n\) дней; температура в \(i\)-й день равна \(a_i\).

Обозначим за среднюю температуру отрезка подряд идущих дней как среднее арифметическое измерений температур, принадлежащих этому отрезку дней. Таким образом, если мы хотим проанализировать среднюю температуру с дня \(x\) по день \(y\), мы будем считать ее как \(\frac{\sum \limits_{i = x}^{y} a_i}{y - x + 1}\) (обратите внимание, что деление производится без округления). Интенсивность температуры — это максимум среди средних температур среди всех отрезков подряд идущих дней длины не менее \(k\). Например, если анализировать измерения \([3, 4, 1, 2]\) и \(k = 3\), интерес представляют отрезки \([3, 4, 1]\), \([4, 1, 2]\) и \([3, 4, 1, 2]\) (мы хотим найти максимальное значение средней температуры среди всех этих отрезков).

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

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

Например, если нам дан массив \([10, 20, 30, 40]\), мы можем переставить числа так, что массив станет \([20, 40, 10, 30]\). При этом на первой и второй позициях числа стали больше (\(20>10\), \(40>20\)), а на третьей и четвёртой — нет, значит для такой перестановки число, которое хочет максимизировать Вася, равно \(2\). Ознакомьтесь с примечанием к первому тестовому примеру, там разобран ещё один показательный тест.

Помогите Васе так переставить числа, чтобы количество позиций, в которых в новом массиве числа больше, чем в изначальном, было максимальным.

В очередной раз Алисе на день рождения вручили массив из \(n\) элементов! Уже третий год кряду!

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

Боб выбрал \(m\) изменений следующего вида. Для некоторых целых чисел \(x\) и \(d\) он выбирает произвольную позицию \(i\) (\(1 \le i \le n\)) и для всех \(j \in [1, n]\) прибавляет \(x + d \cdot dist(i, j)\) к значению \(j\)-й ячейки. \(dist(i, j)\) — это расстояние между позициями \(i\) и \(j\) (т.е. \(dist(i, j) = |i - j|\), где \(|x|\) — модуль числа \(x\)).

Например, если у Алисы в данный момент есть массив \([2, 1, 2, 2]\), и Боб выбирает позицию \(3\) для \(x = -1\) и \(d = 2\), то массив становится \([2 - 1 + 2 \cdot 2,~1 - 1 + 2 \cdot 1,~2 - 1 + 2 \cdot 0,~2 - 1 + 2 \cdot 1]\) = \([5, 2, 1, 3]\). Обратите внимание, что Боб не может выбрать позицию \(i\) вне границ массива (то есть, меньше \(1\) или больше \(n\)).

Алиса будет наиболее счастлива, если элементы массива будут как можно больше. Боб решил, что среднее арифметическое отлично подойдет в качестве метрики.

Какое максимальное значение среднего арифметического Боб может получить?

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

Путь из Москвы в Саратов может быть представлен, как прямая (пожалуй, она не столь ровная в действительности, но в данной задаче будем считать так), и расстояние между Москвой и Саратовом равно \(n\) км. Считаем, что Москва расположена в точке с координатой \(0\) км, а Саратов — в точке с координатой \(n\) км.

Вести машину столь долгое время достаточно утомительно. Формально, если Леха преодолел \(i\) километров после того, как останавливался на отдых в прошлый раз, то сложностью преодоления \((i + 1)\)-го километра он считает величину \(a_{i + 1}\). Гарантируется, что для каждого \(i \in [1, n - 1]\) \(a_i \le a_{i + 1}\). Сложность пути определяется, как сумма сложностей по каждому километру пути.

К счастью, между Москвой и Саратовом могут быть места для отдыха. Каждая целочисленная точка от \(1\) до \(n - 1\) может содержать место для отдыха. Когда Леха заезжает на место для отдыха, он (разумеется) отдыхает, и следующий километр для него становится сложности \(a_1\), километр после этого — сложности \(a_2\) и так далее.

Например, если \(n = 5\) и есть место для отдыха в точке с координатой \(2\), то сложность пути получится \(2a_1 + 2a_2 + a_3\): первый километр будет иметь сложность \(a_1\), второй — \(a_2\), потом Леха отдохнет, и третий километр будет иметь сложность \(a_1\), четвертый — \(a_2\) и последний — \(a_3\). Другой пример: если \(n = 7\) и есть места для отдыха в точках с координатами \(1\) и \(5\), то сложность пути Лехи будет равна \(3a_1 + 2a_2 + a_3 + a_4\).

Леха не знает, какие из целочисленных точек содержат места для отдыха. Поэтому он хочет предусмотреть любую возможную ситуацию. Очевидно, есть \(2^{n - 1}\) вариантов различных распределений точек отдыха (два распределения различны, когда существует такая точка \(x\), что место для отдыха есть ровно в одном из данных распределений). Леха считает все распределения равновероятными. Он хочет посчитать \(p\) — математическое ожидание сложности пути.

Очевидно, \(p \cdot 2^{n - 1}\) — это целое число. Посчитайте его по модулю \(998244353\).

Наташа собирается на ракете полететь на Марс и вернуться на Землю. Также по пути на Марс она приземлится ещё на \(n - 2\) планетах. Формально: пронумеруем все планеты от \(1\) до \(n\). \(1\) — Земля, \(n\) — Марс. Наташа собирается сделать ровно \(n\) полётов: \(1 \to 2 \to \ldots n \to 1\).

Перелёт с планеты \(x\) на планету \(y\) состоит из двух фаз: взлёт с планеты \(x\) и приземление на планету \(y\). Таким образом, полный маршрут поездки выглядит следующим образом: \(1\)-я планета \(\to\) взлёт с \(1\)-й планеты \(\to\) торможение ко \(2\)-й планете \(\to\) \(2\)-я планета \(\to\) взлёт со \(2\)-й планеты \(\to\) \(\ldots\) \(\to\) торможение к \(n\)-й планете \(\to\) \(n\)-я планета \(\to\) взлёт с \(n\)-й планеты \(\to\) торможение к \(1\)-й планете \(\to\) \(1\)-я планета.

Масса ракеты вместе с полезным грузом (но без топлива) равна \(m\) тоннам. Но Наташа не знает, сколько топлива нужно загрузить в ракету. К сожалению, топливо можно загрузить только на Земле, так что, если на какой-то другой планете топливо закончится, то Наташа не сможет вернуться домой. Топливо нужно для взлёта с каждой планеты и для торможения перед каждой планетой. Известно, что \(1\) тонна топлива может поднять с \(i\)-й планеты \(a_i\) тонн груза или затормозить перед \(i\)-й планетой \(b_i\) тонн груза.

Например, если масса ракеты составляет \(9\) тонн, масса топлива \(3\) тонны, а коэффициент при взлёте равен \(8\) (\(a_i = 8\)), то при взлёте сгорит \(1.5\) тоны топлива (так как \(1.5 \cdot 8 = 9 + 3\)). Новая масса топлива после взлёта будет равна \(1.5\) тоннам.

Обратите внимание, что можно использовать нецелый объём топлива при взлёте или посадке. Также, изначальное количество топлива может быть тоже нецелым.

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

Вам дан массив из \(n\) целых положительных чисел \(a_1, a_2, \dots, a_n\). К массиву можно применять следующие операции: выбрать несколько различных индексов этого массива \(i_1, i_2, \dots, i_k\) (\(1 \le i_j \le n\)) и переместить число, стоящее на позиции \(i_1\) на позицию \(i_2\), число стоящее на позиции \(i_2\) на позицию \(i_3\), ..., число на позиции \(i_k\) на позицию \(i_1\). То есть сдвинуть элементы по циклу \(i_1 \to i_2 \to \ldots i_k \to i_1\).

К примеру, если у вас есть \(n=4\), массив \(a_1=10, a_2=20, a_3=30, a_4=40\), и вы выбрали три индекса \(i_1=2\), \(i_2=1\), \(i_3=4\), то получившийся массив будет \(a_1=20, a_2=40, a_3=30, a_4=10\).

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

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

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

Теперь вас интересует следующий вопрос: сколько раз вы перевернете страницу в течение каждого дня? Вы заинтересованы в количестве переворотов страницы в течение каждого дня от \(1\) до \(n\).

Близится следующий сезон, поэтому Вы решили собрать команду из двух или трех человек. У Вас есть \(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\) — наименьшее общее кратное.

Обратите внимание на необычное ограничение по памяти!

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

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

Мы все знаем, что функцию логарифма можно записать как: \(\) \log(p_1^{a_1}p_2^{a_2}...p_k^{a_2}) = a_1 \log p_1 + a_2 \log p_2 + ... + a_k \log p_k \(\) где \(p_1^{a_1}p_2^{a_2}...p_k^{a_2}\) — факторизация простыми числами целого числа. Проблема в том, что эта функция выражается сама через себя, поэтому её сложно вычислять.

По этой причине математики из нейтральной зоны придумали это: \(\) \text{exlog}_f(p_1^{a_1}p_2^{a_2}...p_k^{a_2}) = a_1 f(p_1) + a_2 f(p_2) + ... + a_k f(p_k) \(\)

Заметьте, что \(\text{exlog}_f(1)\) всегда равно \(0\).

Функция \(f\) очень сложная, чтобы дети поняли её, поэтому учителя решили, что функция \(f\) в повседневном использовании может быть представлена как многочлен со степенью не более \(3\) (то есть \(f(x) = Ax^3+Bx^2+Cx+D\)).

"Урок закончен! Не забудьте сделать ваше домашние задание!" Вот оно: \(\) \sum_{i=1}^n \text{exlog}_f(i) \(\)

Помогите детям сделать их домашние задание. Поскольку число может быть очень большим, вам нужно найти ответ по модулю \(2^{32}\).

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

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

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

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

1. Случайным образом равновероятно выбираются два различных активных стартапа \(A\) и \(B\).
2. С равной вероятностью либо \(A\) приобретает \(B\), либо \(B\) приобретает \(A\) (так, если \(A\) приобретает \(B\), то статус \(B\) меняется с активного на приобретенный, и его владельцем становится \(A\)).
3. Когда статус стартапа меняется с активного на приобретенный, все стартапы, которыми он владел, становятся активными.

Например, может произойти следующее. Пусть \(A\) и \(B\) — активные стартапы, \(C\), \(D\), \(E\) — приобретенные с владельцем \(A\), а \(F\), \(G\) — приобретенные с владельцем \(B\):

Активные стартапы показаны красным.

Если \(A\) приобретет \(B\), то будет следующий результат: \(A\), \(F\), \(G\) — активные стартапы, \(C\), \(D\), \(E\), \(B\) — приобретенные с владельцем \(A\), \(F\) и \(G\) не владеют никакими стартапами:

Если же \(B\) приобретет \(A\), то \(B\), \(C\), \(D\), \(E\) будут активными стартапами, \(F\), \(G\), \(A\) будут приобретенными с владельцем \(B\), \(C\), \(D\), \(E\) не будут владеть никаким стартапами:

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

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

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

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

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

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

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

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

Обозначим через \(s(x)\) сумму цифр в десятичной записи положительного целого числа \(x\). По заданным числа \(n\) и \(m\), найдите какие-нибудь положительные целые числа \(a\) и \(b\) такие, что

• \(s(a) \ge n\),
• \(s(b) \ge n\),
• \(s(a + b) \le m\).

Дан набор из \(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\) положительных целых чисел.

Назовем конкатенацией чисел \(x\) и \(y\) такое число, что оно получается при записывании чисел \(x\) и \(y\) подряд без изменения порядка. Например, конкатенация чисел \(12\) и \(3456\) — это число \(123456\).

Посчитайте количество упорядоченных пар позиций \((i, j)\) (\(i \neq j\)) в массиве \(a\) таких, что конкатенация \(a_i\) и \(a_j\) делится на \(k\).

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

Тест состоит из n вопросов, отвечать на них необходимо строго по порядку: с 1-го до n-го. В i-ом вопросе a_i вариантов ответа, ровно один из которых является верным.

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

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

Даны два целых положительных числа \(a\) и \(b\). С ними можно проводить следующие операции:

1. умножить одно из чисел на некоторое простое число \(p\);
2. разделить одно из чисел на некоторое простое \(p\), на которое оно делится.

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

У Алисы есть кусочек ткани. Он имеет форму квадрата, длины сторон которого равны \(a\) сантиметров. А Боб тоже хочет себе кусочек ткани. Он хотел бы себе квадрат, длины сторон которых равны \(b\) сантиметров (при этом \(b < a\)). Алиса хочет сделать Боба счастливым, поэтому она отрежет нужный квадрат в углу её кусочка и отдаст его Бобу. Теперь у неё остался некрасивый кусочек, который имеет форму буквы L (смотрите картинки ниже).

Алиса хочет определить, является ли площадь, выраженная в квадратных сантиметрах, простым числом. Можете ли вы помочь ей это сделать?

У Алисы есть компьютер, который работает с \(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\)-я функция, которую использует «супер функция».

Задан набор из \(2n+1\) целочисленных точек на декартовой плоскости. Точки пронумерованы от \(0\) до \(2n\) включительно. Пусть \(P_i\) — \(i\)-я точка. Тогда \(x\)-координата точки \(P_i\) равна \(i\). \(y\)-координата точки \(P_i\) равна нулю (изначально). Таким образом, изначально \(P_i=(i,0)\).

Заданный набор точек является вершинами графика кусочной функции. \(j\)-й кусок функции — отрезок \(P_{j}P_{j + 1}\). За один ход вы можете увеличить на \(1\) \(y\)-координату любой точки с нечетной \(x\)-координатой (то есть точек \(P_1, P_3, \dots, P_{2n-1}\)). Заметьте, что соответствующие отрезки тоже меняются.

Например, график ниже иллюстрирует функцию для \(n=3\) (количество точек равно \(2\cdot3+1=7\)), в которой мы увеличили \(y\)-координату точки \(P_1\) три раза и \(y\)-координату точки \(P_5\) один раз:

Пусть площадь графика равна площади под графиком, но над координатной прямой OX. Тогда площадь графика на картинке выше равна 4 (голубая площадь на картинке выше — это площадь графика, нарисованного на ней).

Пусть высота графика равна максимальной \(y\)-координате среди всех изначальных точек графика (то есть точек \(P_0, P_1, \dots, P_{2n}\)). Высота графика на картинке выше равна 3.

Ваша задача — найти, какую минимальную высоту может иметь график, состоящий из \(2n+1\) вершин с площадью, равной \(k\). Заметьте, что необязательно минимизировать количество ходов.

Легко заметить, что любой ответ, который может быть получен при помощи применения описанных выше ходов, всегда существует и является целым числом, не превосходящим \(10^{18}\).

Рассмотрим некоторое положительное целое число \(x\). Его разложение на простые имеет вид \(x = 2^{k_1} \cdot 3^{k_2} \cdot 5^{k_3} \cdot \dots\)

Назовем число \(x\) изящным, если наибольший общий делитель последовательности \(k_1, k_2, \dots\) равен \(1\). Например, числа \(5 = 5^1\), \(12 = 2^2 \cdot 3\), \(72 = 2^3 \cdot 3^2\) изящные, а числа \(8 = 2^3\) (\(GCD = 3\)), \(2500 = 2^2 \cdot 5^4\) (\(GCD = 2\)) — нет.

Посчитайте количество изящных чисел от \(2\) до \(n\).

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

Вам дан массив \(a\) из \(n\) целых чисел и целое число \(k\) (\(2 \le k \le n\)), где элементы массива обозначаются как \(a_i\) (\(0 \le i < n\)). Выполните операцию \(z\) определённую ниже над \(a\) и выведите значение \(z(a,k)\) по модулю \(10^{9}+7\).

function z(array a, integer k):
    if length(a) < k:
        return 0
    else:
        b = empty array
        ans = 0
        for i = 0 .. (length(a) - k):
            temp = a[i]
            for j = i .. (i + k - 1):
                temp = max(temp, a[j])
            append temp to the end of b
            ans = ans + temp
        return ans + z(b, k)

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

На каждой из остановок можно прочитать упорядоченный список моментов времени, когда на эту остановку приходит автобус, обозначим как \(a_1 < a_2 < \ldots < a_n\) список для остановки A и как \(b_1 < b_2 < \ldots < b_n\) список для остановки B. Автобусы всегда отъезжают от остановки A и всегда прибывают на остановку B вовремя, но порядок прибытия автобусов может отличаться от порядка отправления. Будем называть порядок прибытия корректным, если для каждого автобуса время его прибытия хотя бы на \(t\) позже, чем время отправления.

Известно, что для соблюдения расписания автобус, отправляющийся в момент времени \(a_i\), должен приехать не позже, чем в момент времени \(b_{x_i}\), то есть \(x_i\)-м по счету. Иными словами, для каждого \(i\) существует такой корректный порядок прибытия автобусов, где \(i\)-й отправленный автобус прибывает \(x_i\)-м (а остальные — как угодно), но не существует корректного порядка, где \(i\)-й отправленный автобус прибывает \((x_i + 1)\)-м.

Формально, назовем перестановку \(p_1, p_2, \ldots, p_n\) корректной, если \(b_{p_i} \ge a_i + t\) для всех \(i\). Тогда \(x_i\) — максимальное значение \(p_i\) среди всех корректных перестановок.

Вам известны числа \(a_1, a_2, \ldots, a_n\) и \(x_1, x_2, \ldots, x_n\), но не известны времена прибытия автобусов. Найдите какое-нибудь подходящее расписание \(b_1, b_2, \ldots, b_n\), или определите, что такого расписания не существует.

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

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

Пусть, например, \(n = 6\) и \(k = 1\). Тогда если Мирослав перевернёт шампур с номером \(3\), то в итоге перевёрнутыми окажутся шампуры с номерами \(2\), \(3\) и \(4\). Если же после этого Мирослав перевернёт шампур с номером \(1\), то перевёрнутыми окажутся шампуры \(1\), \(3\) и \(4\), а шампур \(2\) вернётся в исходное положение (так как перевернется в этой операции).

Как мы уже упоминали выше, искусство приготовления шашлыка требует делать всё вовремя, так что Мирослав хочет научиться переворачивать все \(n\) шампуров за минимальное количество действий. Например, для рассмотренного выше примера \(n = 6\) и \(k = 1\) можно справиться за два действия, просто перевернув шампуры с номерами \(2\) и \(5\).

Помогите Мирославу перевернуть все \(n\) шампуров.

Вам задана зеркальная изнутри труба в виде двух несовпадающих прямых, параллельных оси \(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\).

Ацингел — достаточно маленький городок. В этом городке был всего один доктор — Мисс Ада. Она была очень дружелюбной и никто никогда не говорил про неё ничего плохого. Так что кто мог подумать, что Аду найдут мёртвой в собственном доме? Мистер Гаври, известный во всём мире детектив, был назначен найти преступника. Он опросил \(m\) соседей Ады о клиентах, которые посетили её в тот злосчастный день. Давайте пронумеруем этих клиентов от \(1\) до \(n\). Свидетельством каждого соседа является перестановка этих чисел, которая описывает порядок, в котором этот сосед видел клиентов приходящими к Аде.

Однако некоторые факты выглядят достаточно подозрительно — как могло быть, что, согласно некоторым перестановкам некоторые клиенты были замечены утром, а согласно другим — вечером? «Утром некоторые из соседей скорее всего спали! — подумал Гаври, — А вечером слишком темно, чтобы видеть лица людей...». Теперь он хочет удалить из каждой перестановки некоторый префикс и некоторый суффикс (возможно, пустые) так, что оставшиеся части будут не пусты и равны друг другу. Возможно, часть потенциальных преступников пропадёт, но хотя бы не будет противоречий в свидетельствах соседей.

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

Януш — бизнесмен. Он владеет компанией «Янушзекс», которая производит игры для школьников. Последним хитом Янушзекс является крутая игра для одного человека «Сделай единицу». Игроку дана последовательность из \(n\) целых чисел \(a_i\).

Разрешается выбрать любое подмножество из них и количество очков равно наибольшему общему делителю выбранных чисел. Игроку нужно выбрать наименьшее количество элементов, получив количество очков, равное \(1\). Теперь Януш интересуется, какое минимальное количество элементов нужно выбрать игроку в таком случае?

Ани и Борна играют в короткую игру на многочлене двух переменных. Многочлен имеет специальный вид: одночлены без коэффициентов фиксированы, а на месте всех коэффициентов есть пропуски, которые нужно заполнить, например \(\) \_ xy + \_ x^4 y^7 + \_ x^8 y^3 + \ldots \(\)

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

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

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

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

Сейчас у него есть положительное целое число \(n\). Он хочет разбить \(n\) на \(3\) положительных целых числа \(a,b,c\) так, что \(a+b+c=n\) и никакое из этих \(3\) чисел не делится на \(3\). Помогите ему это сделать.

Задан набор из всех целых чисел от \(l\) до \(r\) включительно, \(l < r\), \((r - l + 1) \le 3 \cdot 10^5\) и \((r - l)\) всегда нечетно.

Вы хотите разделить эти числа на ровно \(\frac{r - l + 1}{2}\) пар таким образом, чтобы в каждой паре \((i, j)\) наибольший общий делитель \(i\) и \(j\) равен \(1\). Каждое число должно встретиться ровно в одной паре.

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

Егор придумал новую головоломку из фишек, в которую предлагает сыграть вам.

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

Для этого можно использовать следующую операцию:

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

Для вас Егор загадал 2 состояния таблицы — начальное и конечное. Гарантируется, что количества нулей и единиц в таблицах совпадают. Ваша задача — с помощью нескольких операций получить из начального состояния конечное. Конечно, Егор не хочет, чтобы количество операций было очень большим. Обозначим за \(s\) количество символов в каждой из таблиц (в таблицах поровну символов). Тогда вы должны использовать не более \(4 \cdot s\) операций.

Вам даны два массива \(a_0, a_1, \ldots, a_{n - 1}\) и \(b_0, b_1, \ldots, b_{m-1}\), и целое число \(c\).

Вычислите следующую сумму:

\(\)\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} a_i b_j c^{i^2\,j^3}\(\)

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

Аркадий и его друзья любят играть в шашки на доске \(n \times n\). Строки и столбцы доски пронумерованы от \(1\) до \(n\).

Друзья недавно выиграли какой-то турнир, поэтому Аркадий хочет поздравить их и подарить конфеты. Вспомнив старинную притчу (но не ее мораль), Аркадий решил дать друзьям по одному набору конфет за каждую клетку доски: набор конфет, соответствующий клетке \((i, j)\), будет состоять из ровно \((i^2 + j^2)\) конфет особенного для этой клетки типа.

Всего друзей, выигравших турнир, \(m\). Сколько же из этих \(n \times n\) наборов конфет можно разделить поровну на \(m\) частей, не разделяя конфеты на части? Обратите внимание, что каждый набор нужно делить независимо, так как конфеты в разных наборах разные.

Назовем преобразованием последовательности из \(n\) элементов следующий процесс:

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

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

Последовательность \(a_1, a_2, \ldots, a_n\) лексикографически больше последовательности \(b_1, b_2, \ldots, b_n\), если существует такой индекс \(i\), что \(a_j = b_j\) для всех \(j < i\), и при этом \(a_i > b_i\).

У вас есть неограниченное количество монет с номиналами \(1, 2, \ldots, n\). Вы хотите выбрать некоторый набор монет имеющий суммарную стоимость \(S\).

Разрешается чтобы в наборе были монеты имеющие одну и ту же стоимость. Какое минимальное количество монет нужно, чтобы набрать сумму \(S\)?

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

• mul \(x\): умножает \(n\) на \(x\) (где \(x\) является произвольным положительным целым числом).
• sqrt: заменяет \(n\) на \(\sqrt{n}\) (эту операцию можно выполнить только если \(\sqrt{n}\) является целым числом).

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

Похоже, что никто в классе не умеет решать эту задачу. Может быть вы можете им помочь?

Вам дано положительное целое число \(n\) большее или равное \(2\). Для пары целых чисел \(a\) и \(b\) (\(2 \le |a|, |b| \le n\)), вы можете преобразовать \(a\) в \(b\) тогда и только тогда, когда существует целое число \(x\), такое что \(1 < |x|\) и (\(a \cdot x = b\) или \(b \cdot x = a\)), где \(|x|\) обозначает модуль числа \(x\).

После такого преобразования ваш счёт увеличивается на \(|x|\) и вам больше не разрешается превращать \(a\) в \(b\) и \(b\) в \(a\).

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

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

Олег по натуре очень любопытен, поэтому он решил установить на южной стороне лабиринта \(n\) лазеров, направленных внутрь лабиринта. На северной стороне лабиринта Олег установил \(n\) приёмников, тоже направленных внутрь лабиринта. Пронумеруем лазеры и приёмники с запада на восток от \(1\) до \(n\). Для каждого лазера известен номер приёмника, в который он должен попасть. Так как в один приёмник не могут попасть одновременно два лазера, то эти номера образуют перестановку — каждый из номеров приёмников встречается ровно один раз.

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

Изучая книгу «Уравнения математической магии» Роман Ойра-Ойра и Кристобаль Хунта обнаружили интересное уравнение: \(a - (a \oplus x) - x = 0\) для заданого \(a\), где знаком \(\oplus\) обозначено побитовое исключающее ИЛИ (XOR) двух чисел (эта операция обозначается как ^ или xor во многих современных языках программирования). Ойра-Ойра быстро нашел \(x\), являющееся решением, однако Кристобалю Хунте результат Ойры-Ойры показался недостаточно интересным, поэтому он спросил коллегу, сколько существует неотрицательных решений данного уравнения. Такая задача оказалась для Ойры-Ойры слишком сложной, поэтому он обратился за помощью к Вам.

Вова собирается поехать на конференцию на поезде. Изначально поезд находится в позиции \(1\), а пункт назначения — позиция \(L\). Скорость поезда равна \(1\) единице длины в минуту (то есть в первую минуту поезд находится в позиции \(1\), во вторую минуту — в позиции \(2\) и так далее).

Также на пути есть фонари. Они расположены в позициях с координатами, делящимися на \(v\) (то есть первый фонарь расположен в позиции \(v\), второй — в позиции \(2v\) и так далее).

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

Вова может увидеть фонарь на позиции \(p\), если \(p\) делится на \(v\) и эту позицию не занимает стоячий поезд (\(p \not\in [l; r]\)). Таким образом, если точка, в которой есть фонарь, является одной из точек, принадлежащих стоячему поезду, Вова не сможет увидеть этот фонарь.

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

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

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

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

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

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

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

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

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

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

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

Задано два целых числа \(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\). К нему применяется следующий алгоритм:

1. если \(n = 0\), то завершить алгоритм;
2. найти наименьший простой делитель \(d\) числа \(n\);
3. вычесть \(d\) из \(n\) и перейти к шагу \(1\).

Определите количество вычитаний, которые совершит алгоритм.

Сейчас лягушка стоит в позиции \(0\) на координатной оси \(Ox\). Она прыгает по следующему алгоритму: первый прыжок — на \(a\) вправо, второй прыжок — на \(b\) влево, третий прыжок — на \(a\) вправо, четвёртый прыжок — на \(b\) влево, и так далее.

Формально:

• если лягушка уже прыгнула четное число раз (перед текущим прыжком), то она прыгает от ее текущей позиции \(x\) в позицию \(x+a\);
• иначе она прыгает от ее текущей позиции \(x\) в позицию \(x-b\).

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

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

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

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

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

Недавно Оля получила магический квадрат размером \(2^n\times 2^n\).

Её сестре кажется, что один квадрат — это скучно, поэтому она попросила Олю, чтобы та выполнила ровно \(k\) операций разбиения.

Операция разбиения — операция, во время которой Оля берет некий квадрат со стороной \(a\) и разрезает его на 4 равных квадрата со стороной \(\dfrac{a}{2}\). Если сторона квадрата равна \(1\), то к нему нельзя применить операцию разбиения (смотрите примеры для лучшего понимания).

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

Условие счастья Оли будет соблюдено, если выполняется следующее утверждение:

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

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

В свободное время Chouti любит выполнять работу по дому. У него есть одно новое задание — покрасить кирпичи во дворе.

На земле выложен ряд из \(n\) кирпичей. У Chouti есть под рукой \(m\) ведер с красками разных цветов, поэтому он покрасил каждый кирпич в один из этих \(m\) цветов.

Закончив красить все кирпичи, Chouti был доволен. Он решил узнать что-нибудь про эти кирпичики. После некоторых подсчетов он обнаружил, что существует ровно \(k\) кирпичей, у которых цвет отличается от цвета кирпича слева (конечно, мы не рассматриваем первый кирпич).

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

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

Chouti нашёл свою идею глупой, потому что, очевидно, эта «сортировка слиянием» иногда не может отсортировать массив правильно. Тем не менее, Chouti теперь хочет оценить, насколько его «сортировка слиянием» хороша. В частности, Chouti хочет узнать для случайной перестановки \(a\) чисел \(1, 2, \ldots, n\) математичекое ожидание числа инверсий после вызова MergeSort(a, 1, n, k).

Можно доказать, что математическое ожидание рационально. Для заданного простого числа \(q\) допустим, что ответ может быть представлен как \(\frac{u}{d}\) где \(gcd(u,d)=1\). Выведите целое число \(r\) удовлетворяющее \(0 \le r<q\) и \(rd \equiv u \pmod q\). Можно доказать, что такое \(r\) существует и уникально.

Вася любит решать уравнения. Сегодня он хочет решить уравнение \((x~\mathrm{div}~k) \cdot (x \bmod k) = n\), где \(\mathrm{div}\) и \(\mathrm{mod}\) означают целочисленное деление и операцию взятия по модулю (см. Примечания ниже для точного определения). В этом уравнении \(k\) и \(n\) являются целыми положительными параметрами, а \(x\) — неизвестным целым положительным числом. Если решений несколько, то Вася хочет найти наименьшее из возможных \(x\). Вы можете ему помочь?

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

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

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

Теперь они хотят высчитать разрушительную мощь пожара. Пусть \(val_{x, y}\) будет секундой, в которую дерево в ячейке \((x, y)\) загорелось. Разрушительная мощь — это сумма \(val_{x, y}\) по всем \((x, y)\) сгоревших деревьев.

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

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