Дан массив \(a\), состоящий из \(n\) целых чисел, и \(q\) запросов к нему. \(i\)-й запрос обозначается двумя целыми числами \(l_i\) и \(r_i\). Для каждого запроса надо найти любое целое число, которое входит ровно один раз в подмассиве массива \(a\), начиная с индекса \(l_i\) и заканчивая индексом \(r_i\) (подмассивом называется непрерывный подотрезок массива). Например, если \(a = [1, 1, 2, 3, 2, 4]\), то в запросе \((l_i = 2, r_i = 6)\) нас интересует подмассив \([1, 2, 3, 2, 4]\), и возможные ответы на запрос — \(1\), \(3\) и \(4\); а в запросе \((l_i = 1, r_i = 2)\) нас интересует подмассив \([1, 1]\), и требуемого элемента не существует.

Можете ли вы ответить на все запросы?

Мальчик Геральд и его тренер Миша играют в интересную игру. В начале игры имеются куча из n конфет и куча из m камней. Геральд и Миша ходят по очереди, первым ходит Миша. Миша на своем ходу проверят, сколько на данный момент Геральд съел конфет и камней. Пусть Геральд съел a конфет и b камней. Тогда Миша начисляет Геральду f(a, b) призовых очков. Геральд же на своем ходу съедает либо одну конфету из кучи с конфетами, либо один камень из кучи с камнями. Когда Миша обнаруживает, что Геральд съел все, кроме одной конфеты и одного камня, он последний раз начисляет очки и игра заканчивается. Опустошать ни ту, ни другую кучку Геральд не имеет права. Расскажите Геральду, как ему играть, чтобы получить наибольшее количество очков: требуется найти один из возможных оптимальных вариантов игры для Геральда.

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

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

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

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

Ильдар взял ленточку и покрасил её в несколько цветов. Формально, ленточка разбита на \(n\) клеточек, каждую из которых он покрасил в один из \(26\) цветов, которые можно обозначить строчными буквами латинского алфавита.

Ильдар решил, что он выберет отрезок ленточки \([l, r]\) (\(1 \le l \le r \le n\)), который ему нравится, и вырежет его из ленточки. Таким образом получится новая ленточка, которую можно условно представить как строку \(t = s_l s_{l+1} \ldots s_r\).

Теперь Ильдар играет в следующую игру — разрезает ленточку \(t\) на несколько новых ленточек и смотрит, сколько среди них различных. Формально, Ильдар выбирает \(1 \le k \le |t|\) индекcов \(1 \le i_1 < i_2 < \ldots < i_k = |t|\) и разрезает \(t\) на \(k\) ленточек-строк \(t_1 t_2 \ldots t_{i_1}, t_{i_1 + 1} \ldots t_{i_2}, \ldots, {t_{i_{k-1} + 1}} \ldots t_{i_k}\) и считает среди них количество различных. Внезапно Ильдара заинтересовал вопрос — а какое минимальное количество различных как строк из них может получиться, при условии что среди этих кусочков хотя бы один вид ленточек повторяется хотя бы два раза? Результатом игры Ильдар считает это число. Если не существует ни одного способа разрезать \(t\) таким образом, то результатом игры будет число -1.

К сожалению, Ильдар ещё не выбрал, какой именно отрезок ему нравится, но у него есть \(q\) отрезков-предпочтений \([l_1, r_1]\), \([l_2, r_2]\), ..., \([l_q, r_q]\). Посчитайте для каждого из отрезков какой будет результат игры нём.

Все автобусные билеты в Берляндии пронумерованы. Номер каждого билета состоит из \(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\).

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

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

• если текущая длина базы хотя бы \(2\), разделить базу на \(2\) равные половины и продолжить их уничтожать независимо, или
• сжечь текущую базу. Если на ней нет мстителей, это отнимает \(A\) единиц энергии, иначе это отнимает \(B \cdot n_a \cdot l\) единиц энергии, где \(n_a\) — число мстителей на этой базе, а \(l\) — длина текущей базы.

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

В городе живут \(m\) людей. Также в городе есть в продаже \(n\) блюд, где \(i\)-е блюде имеет цену \(p_i\), уровень \(s_i\) и симпатичность \(b_i\). У \(j\)-го человека есть доход \(inc_j\) и предпочтительная симпатичность \(pref_j\).

Ни один человек никогда не купит блюдо, уровень которого ниже, чем его доход. Также, ни один человек не может позволить купить себе блюдо, с ценой выше, чем его доход. Иными словами, человек \(j\) может купить блюдо \(i\), если \(p_i \leq inc_j \leq s_i\).

Также человек \(j\) может купить блюдо \(i\), только если \(|b_i-pref_j| \leq (inc_j-p_i)\). Иначе говоря, если цена блюда на \(k\) меньше, чем доход какого-то человека, то этот человек согласен на не более чем \(k\) абсолютную разницу между симпатичностью блюда и предпочитаемой симпатичностью этого человека.

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

Для заданного множества точек на координатной плоскости \(S\) обозначим его расширение \(E(S)\) как результат следующего алгоритма:

Создадим другое множество точек \(R\), изначально равное \(S\). Затем, пока существуют четыре числа \(x_1\), \(y_1\), \(x_2\) и \(y_2\), такие, что \((x_1, y_1) \in R\), \((x_1, y_2) \in R\), \((x_2, y_1) \in R\) и \((x_2, y_2) \notin R\), добавим \((x_2, y_2)\) к \(R\). Когда такую четверку чисел найти будет нельзя, прекратим алгоритм и скажем, что множество \(R\) — результат.

А теперь — сама задача. У вас есть множество \(S\), изначально пустое. Надо обрабатывать два типа запросов: добавить какую-нибудь точку в \(S\), или удалить точку. После каждого запроса выведите, чему равен размер множества \(E(S)\).

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

Вам нужно выполнить \(q\) операций. В \(i\)-й операции у вас есть символ \(s_i\), который равен либо «<», либо «>», и число \(x_i\).

Вы создаете новый массив \(b\) такой, что \(b_j = -a_j\), если \(a_j s_i x_i\) и \(b_j = a_j\) в противном случае (то есть, если \(s_i\) равен «>», то все знаки в \(a_j > x_i\) поменяются). После выполнения всех этих замен значения чисел в массиве \(a\) меняются на значения в \(b\).

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

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

Назовем упорядоченную пару вершин \((x, y)\) (\(x \ne y\)) корректной, если при проходе по простому пути от \(x\) до \(y\) мы никогда не пройдем по \(0\)-ребру после прохода по \(1\)-ребру. Ваша задача — посчитать количество корректных пар в дереве.

Это интерактивная задача. Не забывайте о том, что ваша программа должна каждый раз после вывода запроса сбрасывать буфер вывода. Для сброса буфера вывода можно использовать fflush(stdout) в C++, system.out.flush() в Java, stdout.flush() в Python или flush(output) в Pascal. Если вы используете другой язык программирования, посмотрите в его документации, как выполняется эта операция. Также рекомендуем вам прочесть руководство по интерактивным задачам: https://cf.m27.workers.dev/blog/entry/45307.

Жюри загадало некоторый массив \(a\), состоящий из \(6\) чисел. Существуют \(6\) особых чисел — \(4\), \(8\), \(15\), \(16\), \(23\), \(42\) — и каждое из них встречается в массиве \(a\) ровно один раз (то есть \(a\) — некоторая перестановка этих чисел).

Вы не знаете ничего о их порядке в массиве, но вы можете отправить до \(4\) запросов. В каждом запросе вы выбираете два индекса \(i\) и \(j\) (\(1 \le i, j \le 6\), \(i\) и \(j\) не обязательно должны быть различны), и в ответ вы получите значение \(a_i \cdot a_j\).

Можете ли вы отгадать массив \(a\)?

Массив \(a\) в каждом тесте фиксирован заранее, тестирующая программа не пытается адаптировать его в зависимости от ваших запросов.

До того, как ваша программа даст ответ на задачу, она может отправить до \(4\) запросов. Чтобы задать запрос, выведите одну строку следующего вида: \(?\) \(i\) \(j\), где \(i\) и \(j\) должны быть двумя целыми числами, удовлетворяющими условию \(1 \le i, j \le 6\). Строка, которую вы отправляете, должна заканчиваться символом перевода строки. После отправки запроса программа должна сбросить буфер вывода и прочитать ответ на запрос — строку, содержащую одно целое число \(a_i \cdot a_j\). Если вы отправите некорректный запрос (или отправите более \(4\) запросов), ответом будет строка 0. Если ваша программа получила такой ответ, она должна немедленно завершиться — иначе вы можете получить вердикт «Ошибка исполнения», «Превышено ограничение времени» или какой-нибудь другой, а не «Неправильный ответ».

Чтобы дать ответ на задачу, ваша программа должна отправить строку \(!\) \(a_1\) \(a_2\) \(a_3\) \(a_4\) \(a_5\) \(a_6\) с символом перевода строки в конце. После этого она должна сбросить буфер вывода и завершиться.

Дан неориентированный связный граф G из n вершин и n ребер. G не содержит петель и кратных ребер. Пусть у каждого ребра этого графа есть два состояния: включено и выключено. Изначально все ребра выключены.

Также вам даны m запросов вида (v, u) — изменить состояние всех ребер на кратчайшем пути из вершины v в вершину u в графе G, если таких путей несколько, выбирается лексикографически наименьший. Более формально, рассмотрим все кратчайшие пути из вершины v в вершину u как последовательности вершин v, v₁, v₂, ..., u. Среди таких последовательностей выбирается лексикографически наименьшая.

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

Даны \(n\) отрезков в формате \([l; r]\) на числовой прямой.

Также даны \(m\) запросов в формате \([x; y]\). Какое минимальное число отрезков надо взять так, чтобы каждая точка (не обязательно целочисленная) от \(x\) до \(y\) была покрыта хотя бы одним из них?

Если нельзя выбрать отрезки так, чтобы каждая точка от \(x\) до \(y\) была покрыта, тогда выведите -1 на этот запрос.

Вам задан массив \(a_1, a_2, \dots, a_n\). Вам необходимо разделить его на \(k\) подотрезков (так, что каждый элемент принадлежит ровно одному подотрезку).

Весом подотрезка \(a_l, a_{l+1}, \dots, a_r\) назовем значение \((r - l + 1) \cdot \max\limits_{l \le i \le r}(a_i)\). Весом разбиения — суммарный вес его подотрезков.

Найдите разбиение минимального веса.

Назовем функцию хорошей, если ее область определения — целые числа, и если для любого \(x\) из области определения верно, что если в \(x-1\) функция определена, то \(f(x) = f(x-1) + 1\) либо \(f(x) = f(x-1)\)

Таня нашла \(n\) хороших функций \(f_{1}, \ldots, f_{n}\), которые определены во всех целых точках от \(0\) до \(10^{18}\) включительно, причем \(f_i(0) = 0\) и \(f_i(10^{18}) = L\) для всех \(i\) от \(1\) до \(n\). Также оказалось, что \(L\) делится на \(n\).

Она предложила Алесе сыграть в игру. Алеся может за один вопрос узнать у Тани значение какой-то одной функции в какой-то одной точке. Для того, чтобы выиграть, ей надо для всех \(1 \leq i \leq n\) для \(i\)-й функции выбрать два целых числа \(l_{i}\) и \(r_{i}\) (\(0 \leq l_{i} \leq r_{i} \leq 10^{18}\)), что \(f_{i}(r_{i}) - f_{i}(l_{i}) \geq \frac{L}{n}\), где \(f_i(x)\) обозначает значение \(i\)-й функции в точке \(x\) . Причем надо выбрать такие пары чисел, чтобы никакая пара отрезков \([l_i, r_i]\) не пересекалась (но могут касаться).

К сожалению, Таня не разрешает Алесе задать более \(2 \cdot 10^{5}\) вопросов. Помогите Алесе выиграть!

Можно показать, что всегда можно выбрать такие \([l_i, r_i]\), которые удовлетворяют описанным выше условиям.

Гарантируется, что Таня не изменяет функции в процессе игры, то есть интерактор не адаптивный.

Чтобы узнать значение \(f_i(x)\), в одной строке через пробел выведите символ «?», а затем два целых числа \(i\) и \(x\) (\(1 \leq i \leq n\), \(0 \leq x \leq 10^{18}\)). Не забудьте сделать операцию 'flush', чтобы получить ответ.

В ответ на это считайте целое число, равное значению \(i\)-й функции в точке \(x\).

Вы можете задать не более \(2 \cdot 10^5\) вопросов.

Для сброса буфера вывода (то есть для операции 'flush') сразу после вывода числа или ответа и перевода строки можно сделать:

• fflush(stdout) в языке C++;
• System.out.flush() в Java;
• stdout.flush() в Python;
• flush(output) в Pascal;
• смотрите документацию для других языков.

Взломы:

Для взлома можно использовать только тесты с \(1 \leq L \leq 2000\), для этого задайте тест в следующем формате.

В первой строке должны находиться два целых числа \(n\) и \(L\) (\(1 \leq n \leq 1000\), \(1 \leq L \leq 2000\), \(L\) делится на \(n\))  — число функций и их значение в \(10^{18}\).

В каждой из следующих \(n\) строк должны быть выведены \(L\) чисел \(l_1\), \(l_2\), ... , \(l_L\) (\(0 \leq l_j < 10^{18}\) для всех \(1 \leq j \leq L\) и \(l_j < l_{j+1}\) для всех \(1 < j \leq L\)), в \(i\)-й строке \(l_j\) значит что \(f_i(l_j) < f_i(l_j + 1)\).

У Казака Вуса есть поле с размерами \(n \times m\), которое состоит из «0» и «1». Он строит из этого поля бесконечное поле. Это он делает так:

1. Берет текущее поле и находит для него новое инвертированное поле. Другими словами, в новом поле будет «1» там, где был «0», а «0» там, где был «1».
2. К начальному полю приписывает справа инвертированное поле.
3. К начальному полю приписывает снизу инвертированное поле.
4. К начальному полю приписывает справа снизу начальное поле.
5. Повторяет все это.

Например, если начальное поле было таким:

После первой итерации оно станет таким:

После второй итерации оно станет таким:

И так далее...

Пронумеруем строки сверху вниз от \(1\) до бесконечности, а столбцы слева направо от \(1\) до бесконечности. Назовем подматрицей \((x_1, y_1, x_2, y_2)\) все числа, которые имеют координаты \((x, y)\), такие что \(x_1 \leq x \leq x_2\) и \(y_1 \leq y \leq y_2\).

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

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

(Расстоянием между двумя вершинами называется сумма весов ребер на единственном простом пути между этими двумя вершинами. Диаметр дерева — наибольшее из этих расстояний.)

Подзадача 1 (11 баллов): \(n,q \leq 100\) и \(w \leq 10,000\)

Подзадача 2 (13 баллов): \(n,q \leq 5,000\) и \(w \leq 10,000\)

Подзадача 3 (7 баллов): \(w \leq 10,000\), и все ребра дерева имеют вид \(\{1, i\}\) (То есть граф имеет вид «звезды» с центром в вершине 1.)

Подзадача 4 (18 баллов): \(w \leq 10,000\), и все ребра дерева имеют вид \(\{i, 2i\}\) и \(\{i, 2i+1\}\) (То есть если мы подвесим дерево за вершину 1, то оно будет иметь вид сбалансированного бинарного дерева.)

Подзадача 5 (24 балла): гарантируется, что после каждого обновления по крайней мере один из наидлиннейших простых путей проходит через вершину \(1\)

Подзадача 6 (27 баллов): нет дополнительных ограничений

Вам задано взвешенное дерево, состоящее из \(n\) вершин. Напомним, что деревом называется связный граф без циклов. Вершины \(u_i\) и \(v_i\) соединены ребром веса \(w_i\).

Вам задано \(m\) запросов. \(i\)-й запрос задан целым числом \(q_i\). В этом запросе вам необходимо посчитать количество пар вершин \((u, v)\) (\(u < v\)) таких, что максимальный вес ребра на простом пути между \(u\) и \(v\) не превосходит \(q_i\).

In the galaxy far far away is the ancient interplanetary republic of Bubbleland, consisting of \(N\) planets. Between them, there are \(M\) bidirectional wormholes, each connecting a pair of planets. Bubbleland is a very centralized republic, having a capital planet Whiteplanet, from which any another planet can be reached using these wormholes. It is also guaranteed that no wormhole connects planet to itself and that no two different wormholes connect same pair of planets.

We call a path that begins at one planet, visits other planets and each of them at most once and returns to starting point a tour. Interplanetary Safety Regulations guarantee that each planet belongs to at most one tour and that there are at most \(42\) tours.

After many eons of usage, wormholes need to be repaired and each wormhole has the cost \(W_{i}\) which needs to be payed for reparation. Unfortunately, the Senate of Bubbleland is short on budget. Therefore, they have decided only to fix as many wormholes as they need in order to have all planets reachable from capital and to pay as little money as they have to for this repair. However the way in which the Senate calculates the cost is different. Cost of the set of reparations is binary xor of costs of each individual reparation, that is if reparations to be made have costs \(A_{1},A_{2},...,A_{k}\), the cost of entire set is \(A_{1} \oplus A_{2} \oplus ... \oplus A_{k}\).

Now the Senate would like to know how much money do they have to pay and also the number of different ways to achieve that cost modulo \(1000000007\).

Давайте рассмотрим следующий процесс: изначально у вас есть пустой стек и массив \(s\) длины \(l\). Вы пытаетесь добавлять элементы массива в стек в порядке \(s_1, s_2, s_3, \dots s_{l}\). Причем если стек пустой или элемент на вершине стека не равен текущему, то вы просто добавляете текущий элемент на вершину стека. Иначе вы не добавляете элемент и более того, удаляете верхний элемент стека.

Если после данного процесса стек окажется пустым, то массив \(s\) считается стек-уничтожимым.

Примеры стек-уничтожимых массивов:

• \([1, 1]\);
• \([2, 1, 1, 2]\);
• \([1, 1, 2, 2]\);
• \([1, 3, 3, 1, 2, 2]\);
• \([3, 1, 3, 3, 1, 3]\);
• \([3, 3, 3, 3, 3, 3]\);
• \([5, 1, 2, 2, 1, 4, 4, 5]\);

Давайте рассмотрим изменения стека более подробно при \(s = [5, 1, 2, 2, 1, 4, 4, 5]\) (элемент на вершине текста выделен жирным шрифтом).

1. после добавления \(s_1 = 5\) стек будет равен \([\textbf{5}]\);
2. после добавления \(s_2 = 1\) стек будет равен \([5, \textbf{1}]\);
3. после добавления \(s_3 = 2\) стек будет равен \([5, 1, \textbf{2}]\);
4. после добавления \(s_4 = 2\) стек будет равен \([5, \textbf{1}]\);
5. после добавления \(s_5 = 1\) стек будет равен \([\textbf{5}]\);
6. после добавления \(s_6 = 4\) стек будет равен \([5, \textbf{4}]\);
7. после добавления \(s_7 = 4\) стек будет равен \([\textbf{5}]\);
8. после добавления \(s_8 = 5\) стек станет пустым.

Вам задан массив \(a_1, a_2, \ldots, a_n\). Вам нужно посчитать количество подотрезков этого массива, которые являются стек-уничтожимыми.

Обратите внимание, что вам нужно ответить на \(q\) независимых запросов.

Berland Gardeners United Inc. hired you for the project called "SmartGarden". The main feature of this project is automatic garden watering.

Formally the garden can be represented as a square of \(n \times n\) cells with rows numbered \(1\) to \(n\) from top to bottom and columns numbered \(1\) to \(n\) from left to right. Each cell of the garden contains either a plant or a slab.

It's known that slabs are located on the main diagonal of the matrix representing the garden, and in the cells that are below the main diagonal and share a side with at least one cell of the main diagonal. All the remaining cells of the garden are filled with plants.

Example of the garden for \(n=5\).

During implementation of the project you created a smart robot that takes a list of commands as an input, which are processed one by one. Each command contains:

• a list of horizontal lines (rows in the matrix representing the garden);
• a list of vertical lines (columns in the matrix representing the garden).

While executing each command robot waters only cells in the intersection of specified rows and specified columns. So, if you specify \(r\) rows and \(c\) columns, then exactly \(r \cdot c\) cells will be watered.

In the demo for the customer you have tuned robot in such a way that it waters all the garden. To do that you prepared a single command containing all \(n\) rows and all \(n\) columns.

Unfortunately, 5 hours before the demo for your customer it turned out that the CEO of Berland Gardeners United Inc. was going to take part in it. Moreover, most probably he will be standing on a garden slab during the demo!

Now you need to create a list of commands for the robot so that it waters all the plants and doesn't water any cell containing a slab. Since it's only a beta version of "SmartGarden", the total number of commands shouldn't exceed \(50\).

Create a program that, for a given size of the garden, will find a list of no more than \(50\) commands that allow the robot to water all the plants in the garden without watering the slabs. It is allowed to water a plant several times.

Вам заданы два множества: \(A\) и \(B\). Найдите сумму элементов в множестве \(C = \{x | x = a \oplus b, a \in A, b \in B\}\), по модулю \(998244353\), где \(\oplus\) означает операцию побитовое исключающее ИЛИ. Каждое число должно быть посчитано ровно один раз.

Например, если \(A = \{2, 3\}\) и \(B = \{2, 3\}\) вы должны учесть число \(1\) только один раз, несмотря на то, что вы можете получить его как \(3 \oplus 2\) и как \(2 \oplus 3\). Таким образом, ответ в этом случае будет равен \(1 + 0 = 1\).

Будем называть отрезком \([l; r]\) множество целых чисел вида \(\{l, l+1, \dots, r\}\).

Множество \(A\) задано объединением \(n_A\) отрезков, множество \(B\) задано объединением \(n_B\) отрезков.

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

Для заданного неориентированного помеченного дерева, состоящего из \(n\) вершин, найдите набор отрезков, такой что:

1. концы каждого отрезка являются целыми числами от \(1\) до \(2n\), и каждое целое число от \(1\) до \(2n\) должно встречаться как конец ровно одного отрезка;
2. все отрезки — невырожденные;
3. для каждой такой пары чисел \((i, j)\), что \(i \ne j\), \(i \in [1, n]\) и \(j \in [1, n]\), вершины \(i\) и \(j\) соединены ребром тогда и только тогда, когда отрезки \(i\) и \(j\) пересекаются, но ни отрезок \(i\) не содержится полностью в отрезке \(j\), ни отрезок \(j\) полностью не содержится в отрезке \(i\).

А вы можете решить эту задачу?

Вам задана перестановка \(p_1, p_2, \dots , p_n\) (перестановка — это массив, в котором все числа от \(1\) до \(n\) встречаются ровно один раз). Вес \(i\)-го элемента перестановки равен \(a_i\).

Сначала вы делите вашу перестановку на два непустых множества — префикс и суффикс. Более формально, первое множество содержит элементы \(p_1, p_2, \dots , p_k\), второе — \(p_{k+1}, p_{k+2}, \dots , p_n\), где \(1 \le k < n\).

После этого вы можете перемещать элементы между множествами. Точнее, вы можете выбрать элемент первого множества и переместить его во второе множество или наоборот. Вы заплатите \(a_i\) долларов за перемещение элемента \(p_i\).

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

Например, если \(p = [3, 1, 2]\) и \(a = [7, 1, 4]\), то вам следует действовать следующим образом: разделить \(p\) на две части \([3, 1]\) и \([2]\), а затем переместить элемент, равный \(2\), в первое множество (это будет стоить \(4\)). А если \(p = [3, 5, 1, 6, 2, 4]\), \(a = [9, 1, 9, 9, 1, 9]\), то нужно делать так: разделить \(p\) на две части \([3, 5, 1]\) и \([6, 2, 4]\), а затем переместить элемент, равный \(2\), в первое множество (это стоит \(1\)), а элемент, равный \(5\) — во второе (это также стоит \(1\)).

Посчитайте минимальное количество долларов, которое вам придется потратить.

На координатной оси \(OX\) находятся \(n\) точек. \(i\)-я точка располагается в целочисленной координате \(x_i\) и имеет скорость \(v_i\). Гарантируется, что никакие две точки не располагаются в одной и той же координате. Все \(n\) точек двигаются с неизменной скоростью, координата \(i\)-й точки в момент времени \(t\) (\(t\) может быть нецелым) вычисляется как \(x_i + t \cdot v_i\).

Рассмотрим две точки \(i\) и \(j\). Пусть \(d(i, j)\) равно минимально возможной дистанции между этими двумя точками по всем возможным моментам времени (даже нецелым). Это значит, что если две точки \(i\) и \(j\) совпадут в какой-то момент времени, значение \(d(i, j)\) будет равно \(0\).

Ваша задача — посчитать значение \(\sum\limits_{1 \le i < j \le n}\) \(d(i, j)\) (сумму минимальных дистанций по всем парам точек).

Где-то в дебрях, далеко-далеко находится святая земля, которая имеет форму дерева  — связного неориентированного графа, состоящего из \(n\) вершин и \(n-1\) ребра. Вершины пронумерованы целыми числами от \(1\) до \(n\).

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

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

Ваша задача состоит в том, чтобы найти количество пар путешественников \((i, j)\), удовлетворяющих следующим условиям:

• \(1 \leq i < j \leq m\).
• \(i\)-й и \(j\)-й путешественники станут друзьями.

Это интерактивная задача!

У Ехаба есть загаданная перестановка \(p\) длины \(n\), состоящая из элементов от \(0\) до \(n-1\). По какой-то причине вы хотите выяснить перестановку. Для этого вы можете спросить у Ехаба \(2\) разных индекса \(i\) и \(j\), и он ответит \((p_i|p_j)\), где \(|\) обозначает операцию побитового ИЛИ.

У Ехаба есть достаточно свободного времени, чтобы ответить на \(4269\) вопросов, и, несмотря на то, что ему несложно отвечать на так много вопросов, ему лень играть в ваши глупые игры, поэтому он заранее зафиксирует перестановку и не изменит ее в зависимости от ваших запросов. Можете ли вы угадать перестановку?

Чтобы задать вопрос, выведите "? \(i\) \(j\)" (без кавычек, \(i \neq j\)) Затем вы должны считать ответ, который будет равен \((p_i|p_j)\).

Если мы ответим \(-1\) вместо правильного ответа, это означает, что вы превысили количество запросов или сделали неверный запрос.

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

Чтобы дать ответ, выведите "! \(p_1\) \(p_2\) \(\ldots\) \(p_n\)" (без кавычек). Заметьте, что вывод ответа не считается одним из \(4269\) запросов.

После вывода запроса не забудьте вывести перевод строки, и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Взломы:

Первая строка должна содержать целое число \(n\) (\(3 \le n \le 2^{11}\)) — длину перестановки \(p\).

Вторая строка должна содержать \(n\) целых чисел, разделенных пробелами \(p_1\), \(p_2\), \(\ldots\), \(p_n\) (\(0 \le p_i < n\)) — элементы перестановки \(p\).

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

1. Массив содержит \(n\) (\(1 \le n \le 2 \cdot 10^5\)) элементов.
2. Каждый элемент в массиве \(a_i\) является целым числом в диапазоне \(1 \le a_i \le 10^9.\)
3. Массив отсортирован в порядке неубывания.

Рэй может отправить Омкару серию запросов. Запрос состоит из двух целых чисел, \(l\) и \(r\), таких, что \(1 \le l \le r \le n\). Омкар ответит двумя целыми числами, \(x\) и \(f\). \(x\)  — мода подмассива от индекса \(l\) до индекса \(r\) включительно. Модой массива называют число, которое встречается в нем чаще всего. Если есть несколько чисел, которые встречаются наибольшее количество раз, модой считается наименьшее из них. \(f\)  — это количество раз, которое \(x\) встречается в запрашиваемом подмассиве.

Массив имеет \(k\) (\(1 \le k \le \min(25000,n)\)) различных элементов. Однако из-за грехов Рэя Омкар не скажет Рэю, чему равно \(k\). Рэю разрешено отправить не более \(4k\) запросов.

Помогите Рэю найти его потерянный массив.

Взаимодействие начинается с чтения \(n\).

Затем вы можете сделать один тип запроса:

• "\(? \enspace l \enspace r\)" (\(1 \le l \le r \le n\)) где \(l\) и \(r\) это границы подмассива, который вы хотите запросить.

Ответ на каждый запрос будет иметь вид "\(x \enspace f\)", где \(x\)  — это мода подмассива, а \(f\)  — количество раз, которое \(x\) встречается в подмассиве.

• \(x\) удовлетворяет (\(1 \leq x \leq 10^9\)).
• \(f\) удовлетворяет (\(1 \leq f \leq r-l+1\)).
• Если вы делаете более \(4k\) запросов или нарушаете диапазон номеров в запросе, вы получите вывод "-1."
• Если вы прекратите работу после получения ответа "\(-1\)", вы получите вердикт "Неправильный ответ ". В противном случае вы можете получить произвольный вердикт, потому что ваше решение будет продолжать читать из закрытого потока.

Чтобы вывести ответ, выведите:

• "\(! \enspace a_1 \enspace a_2 \enspace \ldots \enspace a_{n-1} \enspace a_n\)", который является восклицательным знаком, за которым следует массив с пробелом между каждым элементом.

После этого завершите программу. Этот запрос не учитывается в лимит запросов \(4k\).

После вывода запроса не забудьте вывести перевод строки, и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Формат взломов

Для взлома выведите \(1\) целое число в первой строке: \(n\) (\(1 \le n \le 2 \cdot 10^5\)). Во второй строке выведите \(n\) целых чисел \(a_1, a_2, \ldots, a_{n-1}, a_n\), разделенных пробелами. Среди них должно быть не более \(25000\) различных чисел и \(a_j \le a_{j+1}\) должно выполняться для всех \(j\) от \(1\) до \(n-1\).

У вас есть шахматная доска состоящая из \(n\) строк и \(n\) столбцов. Строки пронумерованы снизу вверх от \(1\) до \(n\). Столбцы пронумерованы слева направо от \(1\) до \(n\). Поле находящееся на пересечении \(x\)-го столбца и \(y\)-й строки обозначается как \((x, y)\). Кроме того, \(k\)-й столбец является специальным столбцом.

Изначально доска пуста. Есть \(m\) изменений; \(i\)-е изменение добавляет или удаляет одну пешку. Текущая доска называется хорошей если мы можем переместить все пешки на специальный столбец по следующим правилам:

• Пешку на поле \((x, y)\) можно переместить на поля \((x, y + 1)\), \((x - 1, y + 1)\) или \((x + 1, y + 1)\);
• Вы можете сделать сколько угодно таких ходов;
• Пешки нельзя перемещать за пределы доски;
• В каждом поле не может находится более одной пешки.

Текущая доска может и не быть хорошей. Чтобы исправить это, вы можете добавить дополнительные строки. Эти строки добавляются сверху, т. е. они будут иметь номера \(n+1, n+2, n+3, \dots\).

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

Учёный Иван Иванович изучает перевёрнутые родословные. Перевёрнутая родословная представляет собой набор людей, про каждого из которых известны либо оба его родителя, либо не известен ни один родитель. Кроме того, известно, что у всех людей из родословной есть ровно один ребёнок, кроме одного человека, у которого детей вовсе нет. Поэтому, если пронумеровать людей целыми числами от \(1\) до \(n\), то можно обозначить за \(s_i\) номер ребёнка человека с номером \(i\) и сказать, что \(s_i = 0\) в случае, если у человека с номером \(i\) детей нет.

Назовём человека \(a\) предком человека \(b\), если либо \(a = b\), либо если у \(a\) есть ребёнок, который является предком человека \(b\). Это значит, что человек \(a\) является предком для \(a\), \(s_a\), \(s_{s_a}\) и так далее.

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

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

Вам дана строка \(s[1 \dots n]\), состоящая из строчных латинских букв. Гарантируется, что \(n = 2^k\) для некоторого целого числа \(k \ge 0\).

Строка \(s[1 \dots n]\) называется \(c\)-хорошей, если выполняется как минимум одно из следующих условий:

• Длина строки \(s\) равна \(1\) и она состоит из единственного символа \(c\) (то есть \(s_1=c\));
• Длина строки \(s\) больше \(1\), первая половина строки состоит только из символа \(c\) (то есть \(s_1=s_2=\dots=s_{\frac{n}{2}}=c\)), а вторая половина строки (то есть строка \(s_{\frac{n}{2} + 1}s_{\frac{n}{2} + 2} \dots s_n\)) является \((c+1)\)-хорошей строкой;
• Длина строки \(s\) больше \(1\), вторая половина строки состоит только из символа \(c\) (то есть \(s_{\frac{n}{2} + 1}=s_{\frac{n}{2} + 2}=\dots=s_n=c\)), а первая половина строки (то есть строка \(s_1s_2 \dots s_{\frac{n}{2}}\)) является \((c+1)\)-хорошей строкой.

Например: «aabc» является 'a'-хорошей, «ffgheeee» является 'e'-хорошей.

За один ход вы можете выбрать один индекс \(i\) от \(1\) до \(n\) и заменить \(s_i\) на любую строчную латинскую букву (любой символ от 'a' до 'z').

Ваша задача — найти минимальное количество ходов, необходимое, чтобы получить 'a'-хорошую строку из \(s\) (т.е. \(c\)-хорошую строку для \(c=\) 'a'). Гарантируется, что ответ всегда существует.

Вам нужно ответить на \(t\) независимых наборов тестовых данных.

Еще один пример 'a'-хорошей строки является следующим. Например, рассмотрим строку \(s = \)«cdbbaaaa». Это 'a'-хорошая строка, потому что:

• вторая половина строки («aaaa») состоит только из символов 'a';
• первая половина строки («cdbb») — 'b'-хорошая строка, потому что:
  • вторая половина строки («bb») состоит только из символов 'b';
  • первая половина строки («cd») — 'c'-хорошая строка, потому что:
    • первая половина строки («c») состоит из единственного символа 'c';
    • вторая половина строки («d») — 'd'-хорошая строка.

У вас есть мультимножество, содержащее несколько чисел. Изначально оно содержит \(a_1\) элементов равных \(1\), \(a_2\) элементов равных \(2\), ..., \(a_n\) элементов равных \(n\).

Вы можете применять два типа операций:

• выбрать два числа \(l\) и \(r\) (\(l \le r\)), а затем удалить один элемент, равный \(l\), один элемент, равный \(l + 1\), ..., и один элемент, равный \(r\) из мультимножества. Эта операция может быть применена, только если каждый элемент от \(l\) до \(r\) встречается хотя бы раз в мультимножестве;
• выбрать два числа \(i\) и \(x\) (\(x \ge 1\)), а затем удалить \(x\) элементов равных \(i\) из мультимножества. Эта операция может быть применена, только если в мультимножестве есть как минимум \(x\) элементов, равных \(i\).

За какое наименьшее количество операций можно удалить все элементы из мультимножества?

Вам задан массив \(a\), состоящий из \(n\) неотрицательных целых чисел. Вы должны выбрать неотрицательное целое число \(x\) и сформировать массив \(b\) из \(n\) элементов по следующему правилу: для всех \(i\) от \(1\) до \(n\), \(b_i = a_i \oplus x\) (\(\oplus\) обозначает операцию побитового исключающего ИЛИ).

Назовем инверсией в массиве \(b\) такую пару целых чисел \(i\) и \(j\), что \(1 \le i < j \le n\) и \(b_i > b_j\).

Вы должны выбрать \(x\) таким образом, чтобы количество инверсий в массиве \(b\) было минимально возможным. Если таких \(x\) несколько — выведите минимальное из них.

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

Пикачу — милый и дружелюбный покемон, живущий в стае диких пикачу.

Однако недавно стало известно, что команда R хочет украсть всех этих покемонов! Тренер покемонов Андрей решил помочь Пикачу собрать армию для борьбы с командой R.

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

В качестве армии Андрей может выбрать любую непустую подпоследовательность покемонов. Иными словами, Андрей выбирает какой-то массив \(b\) из \(k\) индексов таких, что \(1 \le b_1 < b_2 < \dots < b_k \le n\), и его армия будет состоять из покемонов с силами \(a_{b_1}, a_{b_2}, \dots, a_{b_k}\).

Сила армии вычисляется как знакопеременная сумма элементов подпоследовательности, то есть \(a_{b_1} - a_{b_2} + a_{b_3} - a_{b_4} + \dots\).

Андрей экспериментирует с построением покемонов. Он \(q\) раз меняет двух покемонов местами, а именно, в \(i\)-й раз он менял местами покемонов с номерами \(l_i\) и \(r_i\).

Андрею надо знать: какую максимальную силу армии он мог получить при начальной расстановке покемонов, а также после каждого изменения строя?

Помогите Андрею и покемонам, иначе команде R удастся воплотить в жизнь свой коварный план!

In Bubbleland a group of special programming forces gets a top secret job to calculate the number of potentially infected people by a new unknown virus. The state has a population of \(n\) people and every day there is new information about new contacts between people. The job of special programming forces is to calculate how many contacts in the last \(k\) days a given person had.

The new virus has an incubation period of \(k\) days, and after that time people consider as non-infectious. Because the new virus is an extremely dangerous, government mark as suspicious everybody who had direct or indirect contact in the last \(k\) days, independently of the order of contacts.

This virus is very strange, and people can't get durable immunity.

You need to help special programming forces to calculate the number of suspicious people for a given person (number of people who had contact with a given person).

There are 3 given inputs on beginning \(n\) where \(n\) is population, \(q\) number of queries, \(k\) virus incubation time in days. Each query is one of three types:

1. (\(x\), \(y\)) person \(x\) and person \(y\) met that day (\(x \neq y\)).
2. (\(z\)) return the number of people in contact with \(z\), counting himself.
3. The end of the current day moves on to the next day.

Смотритель зоопарка покупает коробку фруктов чтобы накормить своего любимца кролика. Фрукты в коробке — это последовательность яблок и апельсинов, которая представляется бинарной строкой \(s_1s_2\ldots s_n\) длины \(n\). В ней \(1\) обозначает яблоко, а \(0\) обозначает апельсин.

Поскольку у кролика аллергия на апельсины, смотритель зоопарка хочет найти наидлиннейшую подряд идующую подпоследовательность яблок. Пусть \(f(l,r)\) — это наибольшая длина подряд идущей подпоследовательности яблок в подстроке \(s_{l}s_{l+1}\ldots s_{r}\).

Помогите смотрителю зоопарка найти \(\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)\). Другими словами, найдите сумму \(f\) по всем подстрокам.

Вам дан массив \(a_1, a_2, \ldots, a_n\) из целых чисел. Этот массив невозрастающий.

Рассмотрим \(n\) магазинов, расположенных в ряд. Магазины пронумерованы целыми числами от \(1\) до \(n\) слева направо. Цена еды в \(i\)-м магазине равна \(a_i\) монет.

Вы должны обработать \(q\) запросов двух видов:

• 1 x y: для всех магазинов \(1 \leq i \leq x\) присвоить \(a_{i} = max(a_{i}, y)\).
• 2 x y: рассмотрим голодного мужчину с \(y\) монетами. Он посещает все магазины с \(x\)-го магазина по \(n\)-й, и если он может купить еду в текущем магазине, он покупает одну порцию этой еды. Найдите, какое количество порций еды он купит. Мужчина может покупать еду в магазине \(i\), если у него есть хотя бы \(a_i\) монет. После покупки количество его монет уменьшается на \(a_i\).

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

Массив пройдет \(i\)-й тест на красоту, если существует способ из изначального массива путем некоторого (возможно, нулевого) количества операций разреза получить массив с суммой элементов, равной \(s_i\).

Операция разреза массива происходит следующим образом:

• Вычисляется \(mid = \lfloor\frac{max(array) + min(array)}{2}\rfloor\), где \(max\) и \(min\) — это функции нахождения максимального и минимального элемента массива. Иными словами, \(mid\) равно сумме максимального и минимального элементов \(array\), деленной на \(2\) с округлением вниз.
• Далее массив разделяется на две части \(\mathit{left}\) и \(right\). В \(\mathit{left}\) попадают все элементы массива, которые имеют значение меньшее либо равное \(mid\), а в массив \(right\) попадают все элементы, которые больше \(mid\). Элементы в \(\mathit{left}\) и \(right\) сохраняют свой относительный порядок, который был в \(array\).
• Третьим шагом выбирается, какой из массивов \(\mathit{left}\) или \(right\) мы хотим оставить. Выбранный массив заменит собой текущий, а другой навсегда удалится.

Вам требуется помочь Майку определить результаты \(q\) тестов на красоту.

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

Даны \(n\) точек на плоскости.

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

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

Перестановка — это последовательность длины \(n\) целых чисел от \(1\) до \(n\), в которой все числа встречаются ровно по одному разу. Например, \([1]\), \([3, 5, 2, 1, 4]\), \([1, 3, 2]\) — перестановки, а \([2, 3, 2]\), \([4, 3, 1]\), \([0]\) — нет.

Поликарпу недавно подарили перестановку \(a[1 \dots n]\) длины \(n\). Поликарпу деревья нравятся больше, чем перестановки, поэтому он хочет превратить перестановку \(a\) в корневое бинарное дерево. Массив различных целых чисел он превращает в дерево следующим образом:

• максимальный элемент массива становится корнем дерева;
• все элементы слева от максимума — образуют левое поддерево (которое строится по тем же правилам, но применяемым для левого участка массива), но если слева от максимума элементов нет, то у корня нет левого сына;
• все элементы справа от максимума — образуют правое поддерево (которое строится по тем же правилам, но применяемым для правого участка массива), но если справа от максимума элементов нет, то у корня нет правого сына.

Например, если он строит дерево по перестановке \(a=[3, 5, 2, 1, 4]\), то корнем будет элемент \(a_2=5\), левым поддеревом будет дерево, которое будет построено для подмассива \(a[1 \dots 1] = [3]\), а правым — для подмассива \(a[3 \dots 5] = [2, 1, 4]\). В итоге будет построено следующее дерево:

Дерево, соответствующее перестановке \(a=[3, 5, 2, 1, 4]\).

Другой пример: пусть перестановка имеет вид \(a=[1, 3, 2, 7, 5, 6, 4]\). В этом случае дерево выглядит так:

Дерево, соответствующее перестановке \(a=[1, 3, 2, 7, 5, 6, 4]\).

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

В компании Dogeforces работают \(k\) сотрудников. У каждого сотрудника, кроме сотрудников нижнего звена, есть не менее \(2\) подчиненных. У сотрудников нижнего звена нет подчиненных. У каждого сотрудника (кроме руководителя компании) есть ровно один непосредственный начальник. Руководитель компании является непосредственным или косвенным начальником всех сотрудников. Известно, что в Dogeforces любой начальник получает зарплату строго больше, чем все его подчиненные.

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

Сбалансированная скобочная последовательность определяется как целая последовательность целых чисел, которая может быть построена по следующим правилам:

• Пустая последовательность сбалансирована.
• Если \([a_1,\ldots,a_n]\) и \([b_1,\ldots, b_m]\) сбалансированы, то их конкатенация \([a_1,\ldots,a_n,b_1,\ldots,b_m]\) сбалансирована.
• Если \(x\) — целое положительное число и \([a_1,\ldots,a_n]\) сбалансирована, то \([x,a_1,\ldots,a_n,-x]\) сбалансирована.

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

Есть \(2n\) карт. Каждая карта имеет число на лицевой стороне и число на оборотной. Каждое целое число \(1,-1,2,-2,\ldots,n,-n\) встречается на лицевой стороне ровно одной карты и на оборотной стороне ровной одной карты (необязательно той же карты).

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

Дан массив \(a\) из \(n\) целых чисел. Стоимость массива \(t\) вычисляется следующим образом:

\(\)cost(t) = \sum_{x \in set(t) } last(x) - first(x),\(\)

где \(set(t)\) есть множество всех различных значений в \(t\) без повторений, \(first(x)\), и \(last(x)\) индексы первого и последнего вхождения \(x\) в \(t\), соответственно. Другими словами, мы считаем сумму расстояний между первым и последним вхождением каждого значения.

Вам нужно разделить \(a\) на \(k\) последовательных отрезков так, что каждый элемент \(a\) принадлежит ровно одному отрезку, а сумма стоимостей отрезков минимальна.

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

Машину можно представлять как перенумерованный \(n\)-мерный гиперкуб. Простым \(n\)-мерным гиперкубом называется неориентированный невзвешенный граф, построенный рекурсивно следующим образом:

• Возьмите два простых \((n-1)\)-мерных гиперкуба. Вершины одного из них должны быть пронумерованы числами от \(0\) до \(2^{n-1}-1\), а другого — от \(2^{n-1}\) до \(2^{n}-1\). Простой \(0\)-мерный гиперкуб — это одна вершина.
• Добавьте ребро между вершинами \(i\) и \(i+2^{n-1}\) для каждого \(0\leq i < 2^{n-1}\).

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

Примеры простого и перенумерованного \(3\)-мерных гиперкубов представлены ниже:

Заметьте, что перенумерованный \(n\)-мерный гиперкуб обладает следующими свойствами:

• Он содержит в точности \(2^n\) вершин.
• Он содержит в точности \(n\cdot 2^{n-1}\) ребер.
• Каждая вершина соединена ровно с \(n\) другими вершинами.
• Он не содержит петель и кратных ребер.

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

У вас с собой есть \(n\) различных цветов, пронумерованных от \(0\) до \(n-1\). Вы хотите покрасить вершины перенумерованного \(n\)-мерного гиперкуба таким образом, чтобы для каждой вершины \(u\), удовлетворяющей \(0\leq u < 2^n\), и каждого цвета \(c\), удовлетворяющего \(0\leq c < n\), существовала хотя бы одна вершина \(v\), соседняя с \(u\) и покрашенная в цвет \(c\). Иными словами, из каждой вершины должно быть возможно перейти в вершину любого цвета ровно по одному ребру.

Дан перенумерованный \(n\)-мерный гиперкуб, найдите любые допустимые перестановку \(P\) и покраску.

Британский математик Джон Литлвуд однажды высказался об индийском математике Сринивасе Рамануджане: «каждое натуральное число было его личным другом».

Оказывается, натуральные числа могут также дружить друг с другом! Вам дан массив \(a\) из различных натуральных чисел.

Будем называть подмассив \(a_i, a_{i+1}, \ldots, a_j\) группой друзей тогда и только тогда, когда существует целое число \(m \ge 2\) такое, что \(a_i \bmod m = a_{i+1} \bmod m = \ldots = a_j \bmod m\), где \(x \bmod y\) обозначает остаток от деления \(x\) на \(y\).