У Алсу есть перестановка $$$p$$$ целых чисел от $$$1$$$ до $$$n$$$. Она хочет разбить $$$p$$$ на две непересекающихся возрастающих подпоследовательности (не обязательно подряд идущих элементов) такие, что разница между длинами этих подпоследовательностей была бы максимально возможной. Заметим, что каждый элемент должен принадлежать хотя бы одной подпоследовательности. Пустая подпоследовательность тоже допустима. Помогите Алсу это сделать.

У Булата есть два целых числа $$$n$$$ и $$$k$$$. Он хочет определить, существует ли массив $$$a_0$$$, $$$a_1$$$, $$$\ldots$$$, $$$a_{n-1}$$$ со следующими свойствами:

• Он содержит все целые числа из интервала $$$[0,n-1]$$$, и каждое целое число встречается ровно один раз.
• Для каждого $$$i \in [0,n-1]$$$ справедливо утверждение $$$(a_i + a_{(i + 2) \pmod n}) \pmod k = 0$$$.

У Алсу есть неориентированный граф с $$$n$$$ вершинами и $$$m$$$ рёбрами. Вершины пронумерованы целыми числами от $$$1$$$ до $$$n$$$. В каждой вершине записано число. В вершине с индексом $$$v$$$ записано число $$$c_v$$$.

Алсу называет прогулкой между вершинами $$$v_1$$$ и $$$v_k$$$ последовательность вершин $$$v_1$$$, $$$v_2$$$, $$$\ldots$$$, $$$v_k$$$ такую, что вершины $$$v_i$$$ и $$$v_{i+1}$$$ связаны ребром для всех $$$1 \leq i \leq k-1$$$. Заметим, что одна и та же вершина и даже одно и то же ребро может встречаться в прогулке несколько раз.

Алсу называет медианой $$$k$$$ чисел $$$\left\lfloor\frac{k}{2}+1 \right\rfloor$$$-е по величине число ($$$1$$$-е по величине число наименьшее). Скобки $$$\lfloor \rfloor$$$ означают округление вниз до ближайшего целого.

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

Помогите Алсу найти минимально возможное число среди медиан всех прогулок от вершины $$$1$$$ до вершины $$$n$$$.

У Булата есть строка $$$s$$$ длины $$$n$$$, которая содержит только строчные буквы английского алфавита (в нижнем регистре). Назовем последовательность букв словом, если она содержит хотя бы одну гласную и хотя бы одну согласную. На какое максимальное число слов Булат может разделить имеющуюся у него строку?

В этой задаче гласными считаются буквы a, i, o, u, e, y, а все остальные согласными.

Булату приснилось, что он работает мороженщиком. Он продаёт порции мороженого, заполняя рожок в форме конуса до некоторого уровня, и кладет поверх него два ароматных шарика мороженого одинакового размера. Он очень щедрый и хочет класть шарики как можно большего размера. Оба шарика должны касаться основной порции мороженого. Шарики могут соприкасаться, но не могут пересекаться. Шарики могут прикасаться к рожку, но не пересекаться с ним. Какой максимальный возможный радиус шариков?

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

Даны

• высота рожка $$$h$$$,
• уровень основной порции мороженого внутри рожка $$$\ell$$$,
• ширина основания рожка $$$w$$$.

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

У Алсу есть полоска бумаги, которая состоит из $$$n$$$ последовательных квадратных клеточек. Клеточки пронумерованы слева направо от $$$1$$$ до $$$n$$$. В каждой клеточке записано одно целое число, которое может принимать значение $$$0$$$, $$$1$$$ или $$$2$$$. Обозначим число в $$$i$$$-й ячейке за $$$a_i$$$. Алсу может покрасить в черный любое количество левых или правых границ этих клеточек (в общем у ячеек $$$n+1$$$ границ). Можно ли покрасить границы клеток так, чтобы количество покрашенных границ у $$$i$$$ клетки равнялось числу $$$a_i$$$?

Например, если в клетках написаны числа $$$1~2~1~0~1~2$$$, то можно покрасить границы следующим образом:

У Булата есть $$$n$$$ строк, и ему надо ответить на $$$q$$$ запросов. Каждый запрос состоит из двух строк $$$l_i$$$ и $$$r_i$$$. Для такого запроса ему нужно подсчитать количество строк из заданного набора таких, что либо $$$l_i$$$ является её префиксом, либо $$$r_i$$$ является её суффиксом, либо выполняются оба условия (таким образом, строка с префиксом $$$l_i$$$ и суффиксом $$$r_i$$$ одновременно считается один раз).

Помогите Булату ответить на запросы.

У Алсу есть дерево с $$$n$$$ вершинами. У каждой вершины $$$v$$$ есть по два значения $$$a_v$$$ и $$$b_v$$$. Алсу хочет обработать $$$q$$$ запросов следующих типов:

1. дана вершина $$$v$$$ и число $$$x$$$, присвоить $$$a_v = x$$$;
2. дана вершина $$$v$$$, вывести $$$a_v$$$;
3. дана вершина $$$v$$$, выполнить следующую процедуру эффективным образом.

   Изначально создать массив $$$\text{used}[1\ldots n]$$$ и заполнить его значениями false. Затем запустить функцию $$$\text{DFS}(v)$$$:

   
       DFS(v):
       {
           used[v] = true;
           for u from 1 to n do
           {
               if (u и v связаны ребром)
                  and (used[u] == false)
                  and (a[v] + b[u] == a[u] + b[v]) then
               {
                   DFS(u);
               }
           }
           a[v] = b[v];
       }
   

Помогите Алсу выполнить эти запросы.

У Булата есть мультимножество целых чисел, которое изначально пусто. Ему нужно обработать $$$q$$$ запросов. Запросы приходят либо на добавление, либо на удаление одного целого числа из мультимножества. После каждого запроса ему необходимо вычислить максимальный возможный МEX мультимножества, который он может получить, если может применять следующие операции. С помощью одной операции можно взять элемент $$$x$$$, который встречается в мультимножестве как минимум дважды, удалить один из них и добавить либо $$$x-1$$$, либо $$$x+1$$$. Эти операции не влияют на мультимножество для следующего запроса.

MEX — это операция, которая означает «минимальный отсутствующий»: MEX мультимножества чисел равен наименьшему неотрицательному целому числу, которого нет в мультимножестве. Например, $$$\text{mex}(\{0,1,1,2,4,4\})=3$$$. Однако, в данной задаче с помощью разрешенных операций мультимножество может быть преобразовано в $$$\{0,1,2,3,4,5\}$$$, у которого MEX уже равен $$$6$$$.

Помогите Булату обработать запросы.

У Алсу есть два массива целых чисел $$$a$$$ и $$$b$$$. Массив $$$a$$$ длины $$$n$$$, а массив $$$b$$$ длины $$$m$$$. Она хочет найти любую матрицу $$$C$$$ размера $$$n \times m$$$ такую, чтобы она удовлетворяла всем указанным условиям:

• Все целые числа из интервала $$$[0,n\cdot m-1]$$$ должны встречаться в $$$C$$$ ровно один раз.
• MEX $$$i$$$-й строки должен равняться $$$a_i$$$,
• MEX $$$j$$$-го столбца должен равняться $$$b_j$$$.

MEX — это операция, которая означает «минимальный отсутствующий»: MEX множества чисел равен наименьшему неотрицательному целому числу, которого нет в множестве. Например, $$$\text{mex}(\{0,1,2,4\})=3$$$.

Помогите Алсу построить такую матрицу.

У Булата есть двоичная последовательность из $$$n$$$ бит $$$a_1$$$, $$$\ldots$$$, $$$a_n$$$ (каждый бит может быть $$$0$$$ или $$$1$$$). Изначально все биты равны $$$0$$$. У Булата также есть $$$m$$$ пар индексов $$$(i,j)$$$ — это допустимые операции, которые можно применить к последовательности. Если он применяет операцию $$$(i,j)$$$, то $$$a_i$$$ меняется на $$$1-a_i$$$, а $$$a_j$$$ меняется на $$$1-a_j$$$.

Кроме того, Булат хочет получить последовательность из $$$n$$$ битов $$$b_1$$$, $$$\ldots$$$, $$$b_n$$$. Можно ли получить $$$b$$$ из $$$a$$$ применяя только допустимые операции (можно также не изменять массив совсем). Каждая из операций может быть применена ноль и или несколько раз, и операции могут быть применены в любом порядке.

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

Затем нижний ящик убирается из хранилища. Другие ящики начинают падать в освободившееся пространство, пока снова не будет достигнуто стабильное расположение. Ящики могут падать по-разному, в зависимости от того, заполняет ли пустой слот левый или правый верхний ящик. Например, на предыдущем рисунке есть 3 разных варианта:

Помогите Булату найти общее количество различных возможных сценариев по модулю $$$10^9+7$$$.

У Алсу есть бесконечная таблица $$$A$$$. Строки и столбцы в ней нумеруется целыми числами $$$0$$$, $$$1$$$, $$$2$$$, и т.д. Число в $$$i$$$-й строке и $$$j$$$-м столбце равно $$$A_{i,j} = 2^i 3^j$$$.

$$$$$$ \begin{array}{c||c|c|c|c|c} & 0 & 1 & 2 & 3 & \ldots \\ \hline\hline 0 & 1 & 3 & 9 & 27 & \ldots \\ \hline 1 & 2 & 6 & 18 & 54 & \ldots \\ \hline 2 & 4 & 12 & 36 & 108 & \ldots \\ \hline 3 & 8 & 24 & 72 & 216 & \ldots \\ \hline \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array} $$$$$$

Помогите Алсу обработать $$$q$$$ запросов вида $$$(i_1,i_2,j_1,j_2)$$$, где $$$i_1 \leq i_2$$$ и $$$j_1 \leq j_2$$$. Для каждого запроса вам нужно вычислить значение

$$$$$$\sum_{i=i_1}^{i_2} \sum_{j=j_1}^{j_2} A_{i,j}$$$$$$ по модулю $$$10^9+7$$$.