В финале чемпионата Берляндии по футболу было показано $$$n$$$ желтых карточек. Известно, что в начале матча в первой команде было $$$a_1$$$ игроков, а во второй команде было $$$a_2$$$ игроков.

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

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

В данной задаче вам задано дерево, состоящее из $$$n$$$ вершин. Дерево — это связный граф, не содержащий циклов. Вершины дерева нумеруются от $$$1$$$ до $$$n$$$.

В заданном дереве есть $$$k$$$ покрашенных вершин с номерами $$$a_1, a_2, \dots, a_k$$$. Выберем произвольную непокрашенную вершину $$$x$$$ и подвесим дерево за эту вершину, то есть будем считать, что вершина $$$x$$$ является корнем дерева. Рассмотрим все поддеревья, корнями которых являются вершины, соединенные ребром с вершиной $$$x$$$. Если в каждом из таких поддеревьев есть хотя бы одна покрашенная вершина, то вершина $$$x$$$ называется интересной.

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

Монокарп выложил на стол слева направо $$$n$$$ шариков, причем цвет $$$i$$$-го слева шарика равен $$$a_i$$$. Он любит порядок, поэтому захотел, чтобы все шарики одного цвета образовывали непрерывные отрезки, причем для каждого цвета этот отрезок был ровно один.

Иными словами, Монокарп хочет расположить шарики так, что для каждого цвета $$$j$$$, если самый левый шарик цвета $$$j$$$ находится в позиции $$$l$$$, а самый правый — в позиции $$$r$$$, то все шарики между позициями $$$l$$$ и $$$r$$$ должны иметь цвет $$$j$$$. Такое расположение шариков Монокарп называет упорядоченным.

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

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

Монокарп и Бикарп живут в Берляндии, где все автобусные билеты состоят из $$$n$$$ цифр, при этом $$$n$$$ — четное число. Гуляя вечером, они нашли билет, некоторые цифры на котором были стерты. Количество позиций, в которых цифры стерты, четно.

Монокарп и Бикарп решили сыграть в игру, используя найденный билет. Монокарп очень не любит счастливые билеты, в то время как Бикарп коллекционирует счастливые билеты. Билет считается счастливым, если сумма первых $$$\frac{n}{2}$$$ цифр билета равна сумме последних $$$\frac{n}{2}$$$ цифр билета.

Монокарп и Бикарп будут ходить по очереди, первый ход сделает Монокарп. На каждом своем ходу игроки будут записывать на место какой-то стертой цифры произвольную цифру от $$$0$$$ до $$$9$$$. Игра заканчивается, когда в билете не останется позиций со стертыми цифрами.

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

Забор состоит из $$$n$$$ досок, расположенных в ряд слева направо. У Монокарпа есть $$$m$$$ типов красок, причем количество досок, на которые хватит краски типа $$$i$$$, равно $$$a_i$$$. Монокарп купил столько красок, что их в точности хватает для покраски всех $$$n$$$ досок, из которых состоит забор. Иными словами, сумма всех $$$a_i$$$ равна $$$n$$$. Каждая доска должна быть покрашена ровно в один цвет.

Монокарп должен покрасить все доски забора таким образом, чтобы максимальная длина отрезка подряд идущих досок, покрашенных в один цвет, не превышала $$$k$$$.

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

В данной задаче вам задана последовательность $$$a_1, a_2, \dots, a_n$$$, состоящая из $$$n$$$ целых чисел.

Перед вами стоит задача найти три числа:

1. количество таких пар индексов $$$(l, r)$$$ $$$(l \le r)$$$, что произведение $$$a_l \cdot a_{l + 1} \dots a_{r - 1} \cdot a_r$$$ строго отрицательно;
2. количество таких пар индексов $$$(l, r)$$$ $$$(l \le r)$$$, что произведение $$$a_l \cdot a_{l + 1} \dots a_{r - 1} \cdot a_r$$$ равно нулю;
3. количество таких пар индексов $$$(l, r)$$$ $$$(l \le r)$$$, что произведение $$$a_l \cdot a_{l + 1} \dots a_{r - 1} \cdot a_r$$$ строго положительно.

У Монокарпа есть две строки $$$s$$$ и $$$t$$$ одинаковой длины, состоящие из латинских букв «a» и «b».

Монокарп хочет сделать строки $$$s$$$ и $$$t$$$ одинаковыми. Для этого он может выполнять следующие операции: выбрать в строке $$$s$$$ позицию $$$pos_1$$$, выбрать в строке $$$t$$$ позицию $$$pos_2$$$ и поменять местами буквы $$$s_{pos_1}$$$ и $$$t_{pos_2}$$$.

Перед вами стоит задача определить минимальное количество операций, которые должен сделать Монокарп, чтобы сделать строки $$$s$$$ и $$$t$$$ одинаковыми, а также вывести сами операции. Если невозможно сделать строки одинаковыми, сообщите об этом.

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

Берляндский проспект можно представить как отрезок координатной прямой с концами в точках $$$0$$$ и $$$10^{18}$$$. В некоторых точках отрезка расположены фонари, $$$i$$$-й фонарь расположен в точке $$$x_i$$$.

Скоро в Бергороде состоится большой студенческий фестиваль, на который съедутся студенты со всех городов Берляндии. Мэр хочет поразить их красотой Берляндского проспекта в ночное время. Для этого в уличное освещение на одну ночь будут внесены изменения следующего характера: будет включена только часть фонарей, а остальные будут отключены, причем включенные фонари будут выбраны таким образом, чтобы Берляндский проспект выглядел красиво.

Конечно же, у всех людей разное представление о красоте. Мэр Бергорода, например, считает, что проспект будет выглядеть красиво, если выполнится следующее условие. Пусть $$$i_1$$$, $$$i_2$$$, ..., $$$i_k$$$ — номера включенных фонарей в порядке возрастания их координат, тогда $$$x_{i_2} - x_{i_1} = x_{i_3} - x_{i_2} = \dots = x_{i_k} - x_{i_{k - 1}}$$$ (то есть, каждая пара соседних включенных фонарей расположена на одинаковом расстоянии). Если будет включено менее $$$3$$$ фонарей, то проспект будет выглядеть красиво вне зависимости от того, где именно будут располагаться эти фонари.

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

Помимо жалоб на уличное освещение, в мэрию Бергорода регулярно поступают жалобы на неполадки с радиовещанием в черте города. Всего в мэрию поступило $$$n$$$ жалоб, подозрительно похожих друг на друга: в $$$i$$$-й жалобе очередной радиолюбитель упоминал две радиостанции $$$x_i$$$ и $$$y_i$$$, сигнал от которых принимается с помехами, и требовал, чтобы хотя бы одна из этих радиостанций распространяла свой сигнал по всему городу.

Конечно же, мэр Бергорода вплотную занялся рассмотрением этих жалоб. Недавно в Бергороде была установлена новая радиовышка, способная распространять сигнал силы от $$$1$$$ до $$$M$$$ (обозначим силу сигнала радиовышки за $$$f$$$). Мэр принял решение выбрать несколько радиостанций и заключить с ними договор, чтобы жители города могли принимать их сигнал. Для заключения договора с $$$i$$$-й радиостанцией необходимо, чтобы соблюдались следующие условия:

• мощность сигнала $$$f$$$ должна быть не менее $$$l_i$$$, иначе в некоторых районах города будет невозможно принимать сигнал $$$i$$$-й радиостанции;
• мощность сигнала $$$f$$$ должна быть не более $$$r_i$$$, иначе сигнал смогут принять жители других населенных пунктов, не заключившие договор с $$$i$$$-й радиостанцией.

Всего этого уже было достаточно, чтобы мэру было трудно выбрать мощность сигнала и радиостанции так, что все жалобы будут удовлетворены. Но позже выяснилось, что некоторые радиостанции могут использовать одни и те же частоты для распространения сигнала: всего существует $$$m$$$ пар радиостанций ($$$u_i$$$, $$$v_i$$$), использующих одни и те же частоты, и для каждой такой пары нельзя одновременно заключить договор с обеими радиостанциями. Если радиостанции $$$x$$$ и $$$y$$$ используют одни и те же частоты, и радиостанции $$$y$$$ и $$$z$$$ используют одни и те же частоты, это не значит, что радиостанции $$$x$$$ и $$$z$$$ используют одни и те же частоты.

Мэру очень трудно проанализировать всю эту информацию и понять, с какими радиостанциями нужно заключать договоры. Помогите ему выбрать такую мощность сигнала $$$f$$$ и такое множество радиостанций, с которыми город заключит договоры, чтобы:

• все жалобы жителей были удовлетворены (формально, для каждого $$$i \in [1, n]$$$ либо с радиостанцией $$$x_i$$$, либо с радиостанцией $$$y_i$$$ заключен договор);
• никакие выбранные радиостанции не конфликтовали за частоты (формально, для каждого $$$i \in [1, m]$$$ либо с радиостанцией $$$u_i$$$, либо с радиостанцией $$$v_i$$$ не заключен договор);
• для каждой выбранной радиостанции соблюдаются условия на мощность сигнала (формально, для каждой выбранной радиостанции $$$i$$$ соблюдается $$$l_i \le f \le r_i$$$).

Монокарп хочет принять участие в $$$n$$$ разных соревнованиях по программированию, в каждом из которых он собирается выиграть футболку. Конечно же, ему не нужно целых $$$n$$$ футболок — он хочет раздать их друзьям. Всего у Монокарпа есть список из $$$n$$$ чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ — размеры футболок, заказанных друзьями. Так совпало, что все $$$a_i$$$ различны.

Чтобы получить все $$$n$$$ футболок для всех $$$n$$$ друзей, Монокарп на каждом соревновании указывает отдельный размер футболки, который он хочет получить — при регистрации на соревнование $$$i$$$ он указывает, что хочет получить футболку размера $$$a_i$$$.

Монокарп уверен в своих навыках программирования, поэтому на каждом соревновании он обязательно выиграет футболку. Однако, к сожалению, он может получить футболку не того размера, который он указал: если он указал размер $$$x$$$, то с вероятностью $$$p$$$ он получит футболку размера $$$x - 1$$$, с вероятностью $$$q$$$ он получит футболку размера $$$x + 1$$$, и с вероятностью $$$1 - p - q$$$ он получит футболку размера $$$x$$$.

После получения всех футболок Монокарп их раздает: для каждого $$$a_i$$$, если он получил хотя бы одну футболку размера $$$a_i$$$, он отдает ровно одну из них другу, заказавшему футболку этого размера. Теперь Монокарп интересуется, скольким друзьям он сможет раздать футболки. Помогите ему посчитать математическое ожидание количества розданных футболок.

Монокарп играет в компьютерную игру Moonbound. Цель игры — спасти галактику от вторжения неизвестной силы при помощи мощного артефакта под названием «Манипулятор материи». Впрочем, Монокарп не занимается спасением галактики — сейчас он просто строит дом для своего персонажа.

Сейчас Монокарпу осталось построить одну из стен своего дома. Весь мир в Moonbound состоит из квадратных блоков, и стена, которую собирается строить Монокарп, — не исключение: она будет квадратной, состоять из $$$n$$$ горизонтальных рядов, в каждом из которых будет по $$$n$$$ блоков (гарантируется, что $$$n$$$ четно). Обозначим позицию, в которой будет находиться $$$j$$$-й блок в $$$i$$$-м ряду, как ($$$i$$$, $$$j$$$).

Монокарп решил построить стену из двух видов кирпича — каменного и песчаного. По мнению Монокарпа, стена будет красивой, если каменные и песчаные блоки будут располагаться в шахматном порядке: левый верхний блок должен быть каменным, блок справа от него — песчаным, блок справа от этого — каменным, и так далее; первый блок во втором ряду — песчаным, второй блок во втором ряду — каменным, и так далее. Формально, если $$$i + j$$$ делится на $$$2$$$, то в позиции ($$$i$$$, $$$j$$$) должен находиться каменный блок, иначе — песчаный.

Манипулятор материи позволяет ставить блоки в двух режимах, но у обоих этих режимов есть особые требования к позициям, в которые ставятся блоки. Назовем позицию ($$$i$$$, $$$j$$$), в которой еще не стоит блок, доступной, если она либо на границе (то есть $$$i = 1$$$, $$$i = n$$$, $$$j = 1$$$ или $$$j = n$$$), либо является соседней по стороне с какой-то позицией, в которой уже стоит блок.

Ставить блоки при помощи манипулятора материи можно двумя способами — либо выбрать какую-то доступную позицию и поставить в нее блок выбранного типа, либо выбрать квадрат $$$2 \times 2$$$, в котором есть хотя бы одна доступная позиция, и заполнить все пустые позиции в этом квадрате блоками одного и того же выбранного типа.

Монокарп хочет построить всю стену за не более чем $$$\frac{3n^2}{4}$$$ применений манипулятора. Если он поставит блок в какую-то позицию, в которой должен находиться блок другого типа, то ему придется разрушать секцию стены, а это займет очень много времени — поэтому он никогда не будет выполнять действие, которое ставит блок неправильного типа на какую-то позицию. Помогите ему составить план действий!

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

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

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

Введем понятие неудобства доступа к принтеру для каждой команды. Пусть команда $$$i$$$ будет участвовать в сборах на этаже $$$f_i$$$ за столом $$$a_i$$$, а принтер установлен на этаже $$$f_p$$$ на столе $$$a_p$$$. Если принтер установлен на том же этаже, на котором участвует команда $$$i$$$ (то есть $$$f_i = f_p$$$), то неудобство доступа к принтеру для команды $$$i$$$ равно $$$|a_i - a_p|$$$. Если принтер установлен на другом этаже (то есть $$$f_i \neq f_p$$$), то неудобство доступа к принтеру для команды $$$i$$$ равно $$$a_i + k + a_p$$$, то есть участникам этой команды нужно дойти до выхода со своего этажа (величина $$$a_i$$$), затем спуститься или подняться по лестнице (величина $$$k$$$) и затем дойти от входа на этаж с принтером до стола с принтером (величина $$$a_p$$$).

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