На улице уже $$$3024$$$ год, идеи для задач давно закончились, а МКОШП теперь проходит в изменённом индивидуальном формате. Жюри выбирают $$$n$$$ задач из всех, которые когда либо существовали, нумеруют их от $$$1$$$ до $$$n$$$, присваивают каждой задаче стоимость $$$a_i$$$, а так же выбирают для каждой задачи некоторый параметр $$$b_i$$$ от $$$1$$$ до $$$n$$$.

Изначально тестирующая система выдаёт участнику первую задачу. Когда участнику выдают $$$i$$$-ю задачу, у него есть два варианта:

• либо он сдаёт задачу и получает $$$a_i$$$ баллов.
• либо он может скипнуть задачу, тогда он никогда не сможет её сдать.

Далее тестирующая система выбирает для участника следующую задачу среди задач с номерами $$$j$$$, такими что:

• если он сдал задачу, она смотрит на задачи с номерами $$$j \lt i$$$.
• если он скипнул задачу, она смотрит на задачи с номерами $$$j \leqslant b_i$$$.

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

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

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

Вася решил сыграть с вами в игру. Он загадывает строку, состоящую из первых $$$k$$$ строчных букв латинского алфавита, после чего выписывает все её непустые суффиксы и сортирует их в лексикографическом$$$^{\dagger}$$$ порядке. Далее он сообщает вам получившийся порядок суффиксов, где суффиксу соответствует позиция в строке, с которой он начинается. Также он сообщает вам, сколько каждой буквы было в исходной строке.

Ваша задача состоит в том, чтобы отгадать загаданную строку.

$$$^{\dagger}$$$Строка $$$s$$$ лексикографически меньше, чем строка $$$t$$$, если есть индекс $$$i$$$ такой, что $$$s_i \lt t_i$$$ (в алфавитном порядке), и $$$s_j = t_j$$$ для всех $$$j \lt i$$$. Иными словами, для первого такого индекса $$$i$$$, где строки различны, $$$s_i \lt t_i$$$. Если такого индекса не существует, то лексикографически меньшей считается строка меньшей длины.

В пустынном городе с холмистым ландшафтом мэрия решила выровнять поверхность дороги, закупив самосвал. Дорога разделена на $$$n$$$ участков, пронумерованных от $$$1$$$ до $$$n$$$ слева направо. Высота поверхности на $$$i$$$-м участке равна $$$a_i$$$. Если высота $$$i$$$-го участка больше $$$0$$$, то самосвал должен забрать песок с $$$i$$$-го участка дороги, а если высота $$$i$$$-го участка меньше $$$0$$$, то самосвал должен засыпать песком яму на $$$i$$$-м участке дороги. Гарантируется, что изначальные высоты не равны $$$0$$$.

Когда самосвал находится на $$$i$$$-м участке дороги, он может либо забрать оттуда $$$x$$$ единиц песка, и тогда высота поверхности на $$$i$$$-м участке уменьшится на $$$x$$$, либо засыпать туда $$$x$$$ единиц песка (при условии, что у него в кузове сейчас есть хотя бы $$$x$$$ единиц песка), и тогда высота поверхности на $$$i$$$-м участке дороги увеличится на $$$x$$$.

Самосвал может начать свой путь на любом участке дороги. Перемещение на соседний слева или справа участок дороги занимает $$$1$$$ минуту, при этом временем загрузки и разгрузки песка можно пренебречь. Кузов самосвала имеет бесконечную вместимость и изначально пуст.

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

Нокотан большой фанат раскрашивания табличек. Она придумала число $$$c$$$ ($$$1 \leq c \leq 17$$$) и решила, что перед входом в здание клуба должна висеть таблица со следующими свойствами:

1. Высота таблицы $$$h$$$ и ширина таблицы $$$w$$$ удовлетворяют ограничениям ($$$1 \leq h, w \leq 1500$$$).
2. Каждая клетка может быть раскрашена в какое-то подмножество из $$$c$$$ цветов (возможно пустое). Формально пусть $$$a_{i, j}$$$ — число, записанное в таблице в клетке с координатами $$$i, j$$$, тогда $$$0 \leq a_{i, j} \lt 2^c$$$ и считается, что клетка покрашена в том числе в цвет с номером $$$k$$$ ($$$0 \leq k \lt c$$$), если $$$\lfloor \frac{a_{i,j}}{2^k} \rfloor \mod 2 = 1$$$.
3. Пусть $$$1 \leq x \lt 2^c$$$ и $$$cnt_x$$$ — число клеток, на которых записано число $$$x$$$. Тогда должно выполняться неравенство $$$1 \leq cnt_x \leq 20$$$.
4. Каждый цвет образует одну компоненту связности. Формально для любого $$$0 \leq k \lt c$$$ клетки, в которых $$$k$$$-й бит записи ненулевой ($$$\lfloor \frac{a_{i,j}}{2^k} \rfloor \mod 2 = 1$$$), образуют одну компоненту связности. (Две клетки находятся в одной компоненте связности, если от одной из них можно добраться до второй, переходя в соседние четыре по горизонтали или вертикали клетки множества).

Помогите Нокотан найти таблицу, удовлетворяющую всем свойствам для заданного $$$c$$$.

Есть вендинговый аппарат, в котором продаётся кола. Всего в аппарате есть $$$n$$$ ячеек. Вы знаете, что изначально в ячейке $$$i$$$ находятся $$$a_i$$$ банок колы. Также в аппарате есть $$$n$$$ кнопок, каждая кнопка соответствует какой-то ячейке, при этом каждой ячейке соответствует ровно одна кнопка. К сожалению, обозначения на кнопках стёрлись, поэтому вы не знаете, какая кнопка соответствует какой ячейке.

Когда вы нажимаете на кнопку, соответствующую ячейке $$$i$$$, из $$$i$$$-й ячейки выпадает одна банка колы, если они там ещё остались. После нажатия банка выпадает так быстро, что отследить, из какой именно ячейки она выпала, невозможно. Содержимое ячеек закрыто от ваших глаз, поэтому вы не можете в реальном времени видеть, сколько банок осталось в каждой из ячеек, единственное, что вам известно, это изначальные количества банок в ячейках: $$$a_1, a_2, \ldots, a_n$$$.

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

Какое минимальное количество нажатий на кнопки нужно произвести, чтобы гарантированно получить хотя бы $$$k$$$ банок колы? Вы можете адаптировать свою стратегию по ходу нажатий, основываясь на том, выпала вам банка или нет. Гарантируется, что всего в аппарате есть хотя бы $$$k$$$ банок колы, иными словами, $$$k \leq a_1 + a_2 + \ldots + a_n$$$.

Подпоследовательность — это последовательность, которую можно получить из массива путем удаления некоторых элементов, не меняя порядок оставшихся элементов. Например, последовательность $$$[1, 3, 6]$$$ — это подпоследовательность массива $$$[1, 2, 3, 6, 4, 5]$$$. Длиной подпоследовательности называют количество элементов в ней.

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

Для массива $$$a$$$ длины $$$n$$$ определим $$$\overline{a_{[l, r]}}$$$ как $$$a_1, \ldots, a_{l - 1}, a_{r+1}, \ldots, a_{n}$$$, то есть весь массив за исключением подотрезка $$$[l, r]$$$.

Наибольшая возрастающая подпоследовательность без подотрезка $$$[l, r]$$$ (НВПБП) — наибольшая возрастающая подпоследовательность массива $$$\overline{a_{[l, r]}}$$$. Обозначим длину этой НВПБП за $$$f(\overline{a_{[l, r]}})$$$.

Дан массив $$$a$$$ длины $$$n$$$. Пусть длина его НВП равна $$$f(a)$$$. Необходимо ответить на $$$q$$$ запросов. Каждый запрос задается парой чисел $$$l, r$$$. В ответ на запрос необходимо вывести, выполняется ли равенство $$$f(a) = f(\overline{a_{[l, r]}})$$$.

Даны $$$n$$$ массивов $$$a_1$$$, $$$\ldots$$$, $$$a_n$$$. Длина каждого массива равна двум. Вам надо склеить массивы в один массив длины $$$2n$$$ так, чтобы количество инверсий$$$^1$$$ в получившемся массиве было как можно меньше. Более формально, вам надо выбрать перестановку $$$p$$$ чисел от $$$1$$$ до $$$n$$$, чтобы массив $$$[a_{p_1,1},\ a_{p_1,2},\ \ldots, a_{p_n,1},\ a_{p_n,2}]$$$ содержал как можно меньше инверсий.

$$$^1$$$ Количество инверсий в массиве $$$b$$$  — это количество пар индексов $$$i$$$ и $$$j$$$, таких что $$$i \lt j$$$ и $$$b_i \gt b_j$$$.

Вам дано два сильносвязных$$$^{\dagger}$$$ ориентированных графа, в каждом из которых ровно $$$n$$$ вершин, но может быть разное количество ребер. Посмотрев на них внимательно, вы заметили важную особенность — длина любого цикла в этих графах делится на $$$k$$$.

Отнесем все $$$2n$$$ вершин к одному из двух классов: $$$\textbf{входящие}$$$ или $$$\textbf{исходящие}$$$. Для каждой вершины вам известен её класс.

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

• Концы любого добавленного ребра лежат в разных графах.
• Из каждой $$$\textbf{исходящей}$$$ вершины исходило ровно одно добавленное ребро.
• В каждую $$$\textbf{входящую}$$$ вершину входило ровно одно добавленное ребро.
• В получившемся графе длина любого цикла делится на $$$k$$$.

$$$^{\dagger}$$$Сильносвязный граф — это граф, в котором из каждой вершины можно добраться до любой другой.

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

Условия в этом казино следующие:

• В казино есть $$$n$$$ игр, в которые предлагается сыграть.
• В каждую из игр можно сыграть не более одного раза.
• Каждая игра характеризуется двумя параметрами: $$$p_i$$$ ($$$1 \le p_i \le 100$$$) и $$$w_i$$$ — вероятность победы в игре в процентах и выигрыш за победу.
• Если вы проиграете хоть в одну игру, в которую решите сыграть, — вы не получите вообще ничего (даже за выигранные игры).

Вам нужно заранее выбрать набор игр, в которые вы будете играть, таким образом, чтобы максимизировать $$$\textbf{матожидание}$$$ выигрыша в казино.

В данном случае, если вы выберете игры с индексами $$$i_1, \dots, i_k$$$, то вы выиграете во все из них с вероятностью $$$\prod\limits_{j=1}^k \frac {p_{i_j}}{100}$$$, и в таком случае получите $$$\sum\limits_{j=1}^k w_{i_j}$$$ выигрыша.

То есть $$$\textbf{матожидание}$$$ вашего выигрыша будет $$$\left(\prod\limits_{j=1}^k \frac {p_{i_j}}{100}\right) \cdot \left(\sum\limits_{j=1}^k w_{i_j}\right)$$$.

Чтобы не разориться, владельцы казино поставили ограничение матожидания выигрыша каждой отдельной игры, так что для любого $$$i$$$ выполнено $$$w_i \cdot p_i \le 200\,000$$$.

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

В сердце древнего королевства растет легендарное Древо Жизни — единственное в своем роде и источник магической силы всего мира. Дерево состоит из $$$n$$$ узлов. Каждый узел этого дерева — это волшебный источник, связанный с другими такими же источниками через магические каналы (ребра). Всего в дереве $$$n-1$$$ каналов, $$$i$$$-й из которых соединяет узлы $$$v_i$$$ и $$$u_i$$$. Также между любыми двумя узлами в дереве существует единственный простой путь по каналам.

Однако магическая энергия, текущая через эти каналы, должна быть сбалансирована, иначе мощь Древа Жизни может нарушить естественный порядок и вызвать катастрофические последствия. Мудрецы королевства обнаружили, что когда два магических канала сходятся в одном узле, между ними возникает опасная «магическая резонансная вибрация». Чтобы защитить Древо Жизни и сохранить его баланс, необходимо выбрать несколько путей и провести через них специальные ритуалы. Путь — это последовательность различных узлов $$$v_1, v_2, \ldots, v_k$$$ для натурального $$$k$$$, где каждая пара соседних узлов $$$v_i$$$ и $$$v_{i+1}$$$ соединена каналом (для любого $$$1 \leq i \leq k - 1$$$). При проведении мудрецами ритуала через такой путь блокируются все резонансные вибрации между парами соседних каналов в пути, а именно между каналами $$$(v_i, v_{i+1})$$$ и $$$(v_{i+1}, v_{i+2})$$$ для каждого $$$1 \leq i \leq k - 2$$$.

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

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

«Не худший» вклад известного банка, который имеет максимальную ставку в линейке вкладов этого банка, можно открыть на сумму от $$$100\,000$$$ рублей, и только если сумма открываемого вклада будет не меньше некоторой величины $$$b$$$, индивидуально рассчитываемой каждому вкладчику банком, исходя из суммы имевшихся вкладов за последние два месяца.

На текущем счету у Филиппа находятся $$$a$$$ рублей, ему очень нравится «Не худший» вклад, поэтому он хочет его открыть на как можно большую сумму. Однако приложение банка позволяет открыть «Не худший» вклад, только если он будет открыт не менее чем на $$$b$$$ рублей.

По счастливой случайности, Лена заметила, что если открыть любой другой вклад на сумму $$$x$$$ из имеющихся на текущем счету средств, то величина $$$b$$$ уменьшится на $$$2x$$$ или станет равна $$$100\,000$$$, если $$$b - 2x \lt 100\,000$$$. При этом закрыть этот другой вклад и вернуть деньги не получится.

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

На какую максимальную сумму Филипп сможет открыть «Не худший» вклад, возможно, сначала используя часть денег для открытия других вкладов.

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