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

Вася знает, что в матрице n строк и m столбцов. Для каждой строки ему известен xor (побитовое исключающее или) всех элементов в этой строке. Последовательность a₁, a₂, ..., a_n задает xor элементов строки под номером 1, 2, ..., n, соответственно. Аналогично, для каждого столбца Вася знает xor всех элементов в столбце. Последовательность b₁, b₂, ..., b_m обозначает xor элементов в столбцах под номерами 1, 2, ..., m, соответственно.

Помогите Васе! Найдите матрицу, которая соответствует этим ограничениям, или скажите, что такой матрицы не существует.

Вирус Хексадесимал очень любит играть с числовыми множествами — пересекать их, объединять. В один прекрасный день она с удивлением обнаружила, что Сказзи, ее ручной сферический кот, объединил все множества в одно и съел результат! Надо было срочно что-то делать, и Хексадесимал полетела на рынок.

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

Но не все так просто! Поскольку в Мэйнфрейме царит рынок совершенной конкуренции, то известно, что объединение любых k множеств содержит не менее k различных чисел (для любого целого положительного k).

Помогите вирусу выбрать подходящий набор множеств. Этот набор может быть пустым.

2969-й год. Прошло 1000 лет с момента посадки на луну. Человечество колонизировало Гиперпространство и жило в гармонии.

Жило, пока мы не поняли, что мы не одни.

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

Последняя надежда Земли — ВЫ!

К счастью, Земля имеет мощную систему защиты, созданную специалистами из MDCS. Флот инопланетян содержит \(N\) кораблей на одной линии. Система защиты состоит из трех типов вооружения:

• SQL-ракеты: каждая SQL-ракета может уничтожить не более одного корабля инопланетян из заданного для каждой ракеты набора.
• лучи Познания: каждому лучу Познания сопоставлен отрезок \([l,r]\), он может уничтожить не более одного корабля инопланетян из этого отрезка.
• OMG-базука: каждая OMG-базука имеет ровно три цели и может уничтожить либо ровно ноль, либо ровно два корабля. Кроме того, система прицеливания является «умной», поэтому множества трех целей для любых двух OMG-базук не пересекаются (таким образом, каждый корабль находится под прицелом не более чем одной OMG-базуки).

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

В стране есть \(n\) городов.

Два кандидата борются за пост президента страны. Выборы состоятся в скором будущем и оба кандидата уже спланировали как они собираются соединить города дорогами. Каждый из планов соединяет города используя ровно \(n - 1\) дорогу. Иначе говоря, каждый план представляет из себя дерево. Оба кандидата также выбрали предлагаемую столицу среди \(n\) городов (\(x\) у первого кандидата, и \(y\) у второго), которая может как совпадать, так и нет.

В каждом городе можно построить порт (в одном городе можно построить не более одного порта). Порт, построенный в \(i\)-м городе принесёт \(a_i\) денег. Однако, у каждого кандидата есть свои специфичные требования, выглядящие следующим образом:

• \(k\) \(x\), что означает, что кандидат хочет построить ровно \(x\) портов в поддереве вершины \(k\) (дерево подвешено за столицу, которую выбрал этот кандидат).

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

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

У Пети есть простой граф (т. е. граф без петель и кратных ребер), состоящий из \(n\) вершин и \(m\) ребер.

Вес \(i\)-й вершины равен \(a_i\).

Вес \(i\)-го ребра равен \(w_i\).

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

Весом подграфа является сумма весов входящих в него ребер минус сумма весов входящих в него вершин. Вам нужно найти подграф данного графа максимального веса. Заданный граф не содержит петель и кратных ребер.

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

Пример холодильника с \(h = 7\) и двумя полками. Полки показаны черным. Рисунок соответствует первому примеру.

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

Алена хочет найти максимальное целое число \(k\) такое, что она может одновременно поставить бутылки с номерами \(1\), \(2\), ..., \(k\) в холодильник. Найдите это наибольшее \(k\).

Вы планируете строить дома на улице. На улице есть \(n\) мест, где вы можете построить дома. Все они пронумерованы слева направо от \(1\) до \(n\). В каждом из них вы можете построить дом с целочисленной высотой от \(0\) до \(h\).

За каждый дом вы получаете прибыль в размере \(a^2\) долларов, где \(a\) — высота этого дома.

У города есть \(m\) ограничений. \(i\)-е ограничение говорит о том, что если самый высокий дом от \(l_i\) до \(r_i\) строго больше, чем \(x_i\), вы должны заплатить штраф в размере \(c_i\) долларов.

Вы хотели бы построить дома, чтобы максимизировать свою чистую прибыль (прибыль минус штрафы). Определите максимально возможную прибыль.

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

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

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

Всего у империи есть \(s\) космических кораблей, а у повстанцев есть \(b\) баз, расположенных на различных планетах галактики.

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

У каждой базы есть местоположение \(x\) и уровень защиты \(d\).

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

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

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

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

Таким образом, для каждой атакованной базы повстанцы теряют по \(k\) золота.

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

Разумеется, фейковые базы не содержат золота, но создание одной такой базы стоит \(h\) золота.

Какое минимальное количество золота повстанцы потеряют, если они создадут оптимальное количество фейковых баз?

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

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

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

• в самом начале недовольство равно \(0\);
• когда участник встречи приходит к перекрестку \(1\), недовольство увеличивается на \(c \cdot x\), где \(c\) — некоторая заданная константа, а \(x\) — количество минут, которое потребовалось человеку, чтобы достичь перекрестка \(1\);
• когда \(x\) участников организации идут по одной и той же улице в одну и ту же минуту в одном и том же направлении, к недовольству прибавляется \(dx^2\), где \(d\) — некоторая заданная константа. Например, если два человека идут по одной и той же улице в одну и ту же минуту в одном и том же направлении, к недовольству добавляется \(4d\) (не \(5d\)).

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

Сокровища! Кто не мечтал о них в детстве? Именно так подумал юный Вася и отправился в длительное путешествие к Острову Сокровищ.

Остров Сокровищ представляет собой прямоугольное поле \(n \times m\), окруженное океаном. Пронумеруем строки поля последовательными целыми числами от \(1\) до \(n\) сверху вниз, а столбцы последовательными целыми числами от \(1\) до \(m\) слева направо. Обозначение \((r, c)\) соответствует клетке, расположенной в строке \(r\) и столбце \(c\). В некоторых клетках острова растут непроходимые леса, а остальные клетки свободные и проходимые. Сокровище закопано в клетке \((n, m)\).

Вася высадился с корабля в клетку \((1, 1)\). Теперь он хочет добраться до сокровища. Вася сильно спешит за сокровищем, поэтому может перемещаться только в клетку в следующей строке (вниз) или следующем столбце (вправо), то есть из клетки \((x, y)\) он может сделать ход только в клетки \((x+1, y)\) и \((x, y+1)\). Конечно, Вася не может заходить в клетки, где растёт непроходимый лес.

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

Помогите Злой Ведьме определить, на каком минимальном количестве клеток ей придётся вырастить непроходимый лес, чтобы Вася не смог добраться до сокровища?

There are \(N\) cities in the country of Numbata, numbered from \(1\) to \(N\). Currently, there is no road connecting them. Therefore, each of these \(N\) cities proposes a road candidate to be constructed.

City \(i\) likes to connect with city \(A_i\), so city \(i\) proposes to add a direct bidirectional road connecting city \(i\) and city \(A_i\). It is guaranteed that no two cities like to connect with each other. In other words, there is no pair of integers \(i\) and \(j\) where \(A_i = j\) and \(A_j = i\). It is also guaranteed that any pair of cities are connected by a sequence of road proposals. In other words, if all proposed roads are constructed, then any pair of cities are connected by a sequence of constructed road.

City \(i\) also prefers the road to be constructed using a specific material. Each material can be represented by an integer (for example, \(0\) for asphalt, \(1\) for wood, etc.). The material that can be used for the road connecting city \(i\) and city \(A_i\) is represented by an array \(B_i\) containing \(M_i\) integers: \([(B_i)_1, (B_i)_2, \dots, (B_i)_{M_i}]\). This means that the road connecting city \(i\) and city \(A_i\) can be constructed with either of the material in \(B_i\).

There are \(K\) workers to construct the roads. Each worker is only familiar with one material, thus can only construct a road with a specific material. In particular, the \(i^{th}\) worker can only construct a road with material \(C_i\). Each worker can only construct at most one road. You want to assign each worker to construct a road such that any pair of cities are connected by a sequence of constructed road.

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

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

Иными словами, каждая из сетей является отдельным корневым ориентированным деревом с \(n\) листьями и с корнем в вершине \(1\). В каждом дереве свои вершины и своя независимая нумерация вершин.

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

В этом примере основная сеть содержит \(6\) узлов (изображена сверху), а запасная — \(4\) узла (изображена снизу). Количество приборов равно \(3\), они пронумерованы синим цветом.

Гарантируется, что вся электросеть (две сети и \(n\) приборов) может быть изображена на схеме способом, аналогичным картинке выше:

• основная сеть будет составлять дерево сверху, в котором все провода ведут в направлении «сверху вниз»,
• запасная сеть будет составлять дерево снизу, в котором все провода ведут в направлении «снизу вверх»,
• приборы — горизонтальный ряд между ними, пронумерованный от \(1\) до \(n\) слева направо,
• провода между узлами сетей изображены непересекающимися отрезками.

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

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

Вам задан двудольный граф: первая доля графа содержит \(n_1\) вершин, вторая — \(n_2\) вершин, а также в графе \(m\) ребер. Граф может содержать кратные ребра.

Первоначально, все ребра графа бесцветные. Каждое ребро вы можете либо оставить бесцветным (это бесплатно), либо покрасить в красный (стоимость данного действия \(r\) монет), либо покрасить в синий (за \(b\) монет). Никакое ребро не может быть покрашено в оба цвета одновременно.

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

• у каждой красной вершины количество смежных с ней красных ребер должно быть строго больше, чем смежных с ней синих ребер;
• у каждой синей вершины количество смежных с ней синих ребер должно быть строго больше, чем смежных с ней красных ребер.

Бесцветные вершины не накладывают никаких ограничений.

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

Еще одна характерная черта языка Shakespeare — то, что переменные называются именами персонажей пьес Шекспира, а все действия над ними (изменение значений, вывод на печать и так далее) производятся в виде диалога с другими персонажами. Кроме того, новые значения переменных задаются довольно громоздко, поэтому их использование обычно стараются свести к минимуму.

Нам нужно вывести на печать заданную последовательность n натуральных чисел. Для этого у нас есть m персонажей-переменных и два вида действий над ними:

• variable=integer
• print(variable)

В качестве variable может выступать любая из m переменных. Переменные обозначаются строчными латинскими буквами от «a» до «z» включительно. В качестве integer может выступать любое натуральное число.

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

Это более простая версия задачи H без запросов на изменение.

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

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

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

• Каждый провод должен соединять красный и синий порт, и каждый порт может быть соединён не более чем одним проводом.
• Каждый участок провода должен быть горизонтальным либо вертикальным, и повороты возможно только в одном из контактов.
• Чтобы избежать интерференции, провода не должны иметь общих частей ненулевой длины (однако, они могут проходить через общие контакты). Кроме того, провод не может покрывать один участок ненулевой длины дважды.

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

До этого места условия обеих версий задачи совпадают. Различия начинаются ниже.

Помогите Лестеру и Делберту найти пропускную способность платы с данной конфигурацией.

Кирпич  — прямоугольник с целыми сторонами шириной \(1\) или высотой \(1\) (или и то и другое).

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

Пример замощения с первого примера с использованием \(5\) кирпичей. Существует также замощение из \(4\) кирпичей.

Какое минимальное количество кирпичей необходимо для замощения данной сетки?

В очередной скучный день карантина BThero принялся изучать матрицы размера \(n \times m\). Строки матрицы нумеруются от \(1\) до \(n\) сверху вниз, а столбцы нумеруются от \(1\) до \(m\) слева направо. Клетка в \(i\)-й строке и \(j\)-м столбце обозначается \((i, j)\).

Для каждой клетки \((i, j)\) матрицы у BThero были два значения:

1. ценность данной клетки, которая выражается одним положительным целым числом;
2. направление данной клетки, которое выражается одним из символов L, R, D, U. Данные символы означают переходы в соседние клетки \((i, j - 1)\), \((i, j + 1)\), \((i + 1, j)\), \((i - 1, j)\), соответственно. Никакой переход не вел за границу матрицы.

Назовем клетку \((i_2, j_2)\) достижимой из \((i_1, j_1)\), если, начав из клетки \((i_1, j_1)\) и переходя в соседнюю клетку в соответствии с направлением текущей клетки, мы рано или поздно посетим \((i_2, j_2)\).

BThero решил создать еще одну матрицу из имеющихся двух. Для клетки \((i, j)\) обозначим \(S_{i, j}\) как множество достижимых из нее клеток (включая саму клетку \((i, j)\)). Значение новой матрицы в клетке \((i, j)\) будет равно сумме ценностей всех клеток из \(S_{i, j}\).

Быстро посчитав новую матрицу, BThero разослал ее всем своим друзьям. Однако он не сохранил обе изначальные матрицы! Помогите ему восстановить любые две изначальные матрицы, из которых могла получиться заданная.

Аня и Боря решили сыграть в игру «Камень, ножницы, бумага».

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

• если один игрок показал камень, а другой ножницы, то игрок, показавший камень, объявляется победителем раунда, а другой игрок — проигравшим;
• если один игрок показал ножницы, а другой бумагу, то игрок, показавший ножницы, объявляется победителем раунда, а другой игрок — проигравшим;
• если один игрок показал бумагу, а другой камень, то игрок, показавший бумагу, объявляется победителем раунда, а другой игрок — проигравшим.

Аня и Боря решили, что они сыграют ровно \(n\) раундов описанной игры. Аня решила, что она \(a_1\) раз покажет камень, \(a_2\) раз покажет ножницы и \(a_3\) раз покажет бумагу. Боря решил, что он \(b_1\) раз покажет камень, \(b_2\) раз покажет ножницы и \(b_3\) раз покажет бумагу. При этом ни Аня, ни Боря еще не выбрали последовательность, в которой будут показывать предметы. Гарантируется, что \(a_1 + a_2 + a_3 = n\) и \(b_1 + b_2 + b_3 = n\).

Перед вами стоит задача определить два числа:

1. минимальное количество раундов, которое может выиграть Аня;
2. максимальное количество раундов, которое может выиграть Аня.

Дан ориентированный ацикличный граф (ориентированный граф, не содержащий циклов) из \(n\) вершин и \(m\) дуг. \(i\)-я дуга ведет из вершины \(x_i\) в вершину \(y_i\) и имеет вес \(w_i\).

Ваша задача — для каждой вершины \(v\) выбрать некоторое целое число \(a_v\), после чего на каждой дуге \(i\) записать такое число \(b_i\), что \(b_i = a_{x_i} - a_{y_i}\). Вы должны выбрать числа таким образом, чтобы:

• все \(b_i\) были положительны;
• значение выражения \(\sum \limits_{i = 1}^{m} w_i b_i\) было минимально возможным.

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

Артем строит нового робота. У него есть таблица \(a\), состоящая из \(n\) строк и \(m\) столбцов. Ячейка, расположенная на \(i\)-й сверху строке и \(j\)-м слева столбце, содержит значение \(a_{i,j}\).

Если две соседние ячейки таблицы содержат одинаковое значение, то робот ломается. Таблица называется хорошей, если никакие две соседние клетки не содержат одинаковое значение. Две клетки называются соседними, если они имеют общую сторону.

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

Более формально, найдите хорошую таблицу \(b\), которая удовлетворяет следующему условию:

• Для всех подходящих (\(i,j\)) выполняется или \(b_{i,j} = a_{i,j}\), или \(b_{i,j} = a_{i,j}+1\).

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

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

Задано целое число \(n\) и две последовательности \(a_1, a_2, \dots, a_n\) и \(b_1, b_2, \dots, b_n\).

Назовем множество целых чисел \(S\) такое, что \(S \subseteq \{1, 2, 3, \dots, n\}\) странным, если для каждого элемента \(i\) из \(S\) выполняется следующее условие: для каждого \(j \in [1, i - 1]\), если \(a_j\) делит \(a_i\), то \(j\) также входит в \(S\). Пустое множество является странным.

Стоимостью множества \(S\) назовем величину \(\sum\limits_{i \in S} b_i\). Вам необходимо найти максимальную возможную стоимость странного множества.

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

Ну, теперь угадайте, что случилось. На острове \(1\) был открыт портал в мир демонов. Сейчас начало \(1\)-го дня катастрофы, и все \(k\) магов собрались на острове \(1\) (они пытались закрыть портал, но поняли, что это невозможно). В начале \(2\)-го дня гигантская орда демонов выйдет из портала, захватит остров \(1\) и убьет каждого мага, оставшегося на этом острове. В течение каждого дня \(i\), если остров \(v\) был захвачен демонами к началу дня, орда демонов будет путешествовать по всем таким мостам, одним из концов которых является \(v\), захватывать каждый остров, который они достигнут, и убивать каждого мага, которого они встретят на своем пути.

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

• потратить один день для пересечения одного из мостов, соединенных с островом, где в настоящее время находится маг. Проходя через мост, маг может забрать с него магический камень (если таковой имеется; каждый магический камень может быть поднят не более чем одним магом). Если мост будет пройден демонами в тот же день, или к началу следующего дня тот остров, на который отправляется маг, будет уже захвачен демонической ордой (даже если они прибудут туда в тот же момент), и маг будет убит.
• выполнить ритуал телепортации, чтобы добраться до безопасного места за пределами Даларана. Этот ритуал потребляет два магических камня (и не может быть выполнен, если у мага меньше двух камней).

Каждый магический камень распадается за \(2\) дня — если его поднять в середине дня \(i\), он распадается в середине дня \(i + 2\). Если камень распался, то его нельзя использовать в ритуале телепортации.

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

Алиса и Боб играют в игру. У Алисы есть \(n\) сундуков с сокровищами (в \(i\)-м лежит \(a_i\) монет) и \(m\) ключей (\(j\)-й из которых она может продать Бобу за \(b_j\) монет).

Сначала Алиса вешает некоторые замки на сундуки. Есть \(m\) типов замков, замок \(j\)-го типа можно открыть только \(j\)-м ключом. Чтобы повесить замок типа \(j\) на \(i\)-й сундук, Алиса должна заплатить \(c_{i,j}\) долларов. Алиса может повесить произвольное количество различных замков на каждый сундук (возможно, ноль).

Затем Боб покупает у Алисы несколько ключей (возможно, ноль или все) и открывает все сундуки, которые он может открыть (он может открыть сундук, если у него есть ключи от всех замков на этом сундуке). Прибыль Боба — это разность между суммарным количеством монет в открытых сундуках и суммарным количеством монет, которые он тратит на покупку ключей у Алисы. Если прибыль Боба строго положительная (больше ноля), то он выигрывает игру. Иначе Алиса выигрывает игру.

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

Монокарп играет в компьютерную игру «Гоблины и гномы». В этой игре он управляет подземным городом гномов, защищающимся от орд гоблинов.

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

На город готовится \(k\) атак гоблинов, в \(i\)-й атаке город атакуют \(i\) гоблинов. Цель Монокарпа — выдержать все \(k\) атак.

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

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

Если в результате атаки все залы оказались разграблены — Монокарп проигрывает. Иначе гномам удается восстановить город. Если какой-то зал оказался разграблен в ходе атаки, то в ходе следующих атак он все равно представляет интерес для гоблинов (гномы успевают восстановить его).

Перед каждой атакой у Монокарпа есть время для подготовки. Монокарп может готовиться бесконечно долго (он сам решает, когда вызвать каждую атаку), но чем дольше он готовится к атаке, тем меньше очков он получает. Если Монокарп готовился к \(i\)-й атаке \(t_i\) минут, то после нее он получает \(\max(0, x_i - t_i \cdot y_i)\) очков (естественно, если он не проигрывает).

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

Помогите Монокарпу выдержать все \(k\) атак гоблинов и набрать максимальное количество очков!

Ирина работает в экскурсионной компании Саратова. Сегодня она собирается организовать экскурсии по городам Саратов и Энгельс.

Всего существует \(n_1\) достопримечательность в Саратове и \(n_2\) достопримечательность в Энгельсе. Города разделены рекой, но есть \(m\) автобусных маршрутов, которые проходят по мостам и позволяют туристам добраться из Саратова в Энгельс и обратно. Маршрут \(i\)-го автобуса проходит от \(x_i\)-й достопримечательности в Саратове до \(y_i\)-й достопримечательности в Энгельсе, а также в обратном направлении.

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

Каждый турист начинает свой экскурсионный день с какой-нибудь достопримечательности Саратова, \(k_i\) туристов начинают с \(i\)-й достопримечательности. Затем гиды везут их в Энгельс: на каждой достопримечательности Саратова гид выбирает автобусный маршрут, ведущий от этой достопримечательности в Энгельс, и все туристы, отправляющиеся с этой достопримечательности, отправляются в Энгельс по этому автобусному маршруту. После завершения экскурсий в Энгельсе происходит то же самое: для каждой достопримечательности в Энгельсе гид выбирает автобусный маршрут, ведущий от этой достопримечательности в Саратов, и все туристы с этой достопримечательности отправляются в Саратов по этому автобусному маршруту.

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

В местном бридж-клубе сейчас спорят на \(n\) различных тем, пронумерованных от \(0\) до \(n-1\), и, вот совпадение, в клубе состоят ровно \(2^n\) игроков, пронумерованных от \(0\) до \(2^n-1\). Никакие два игрока не имеют полностью совпадающих взглядов на все \(n\) тем, а именно, у \(i\)-го игрока положительный взгляд на \(j\)-ю тему, если \(i\ \&\ 2^j > 0\), и отрицательный взгляд иначе. Здесь \(\&\) обозначает операцию побитового И.

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

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

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

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

При этом у вас есть \(m\) ограничений на получившиеся вклады. Каждое ограничение задается упорядоченной парой \((u, v)\), означающей, что в финальный вклад оленя \(u\) должен быть меньше или равен финального вклада оленя \(v\).

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

Дан неориентированный граф, состоящий из \(n\) вершин, пронумерованных от \(1\) до \(n\). Вершина \(i\) имеет значение \(a_i\), все \(a_i\) попарно различны. Между вершинами \(u\) и \(v\) есть ребро, если либо \(a_u\) делит \(a_v\), либо \(a_v\) делит \(a_u\).

Найдите минимальное количество вершин, которое нужно удалить, чтобы граф стал двудольным. При удалении вершины удаляются все инцидентные ей ребра.

You are organizing a training camp to teach algorithms to young kids. There are \(n^2\) kids, organized in an \(n\) by \(n\) grid. Each kid is between \(1\) and \(n\) years old (inclusive) and any two kids who are in the same row or in the same column have different ages.

You want to select exactly \(n\) kids for a programming competition, with exactly one kid from each row and one kid from each column. Moreover, kids who are not selected must be either older than both kids selected in their row and column, or younger than both kids selected in their row and column (otherwise they will complain). Notice that it is always possible to select \(n\) kids satisfying these requirements (for example by selecting \(n\) kids who have the same age).

During the training camp, you observed that some kids are good at programming, and the others are not. What is the maximum number of kids good at programming that you can select while satisfying all the requirements?

Принято считать, что самый известный алгоритм нахождения наибольшего общего делителя двух чисел придумал Евклид, однако на самом деле этот алгоритм придумала именно Тётя Люсине. Вы, должно быть, уже не удивились, ведь она — величайший ум человечества. И теперь она решила модернизировать этот алгоритм, привнеся в него немного креатива. А в вас есть эта жилка креатива?

Рассмотрим алгоритм Люсине для нахождения наибольшего общего делителя, где \(t\) это некоторый список:

function Euclid(a, b):
    if a < b:
        swap(a, b)

    if b == 0:
        return a

    r = остаток от деления a на b
    if r > 0:
        добавить r в конец t

    return Euclid(b, r)

Существует массив \(p\) пар положительных целых чисел, каждое из них не больше \(m\). Изначально список \(t\) пустой. Описанная выше функция запускается на каждой паре из массива \(p\). После этого вам даётся перестановка элементов \(t\).

Вам необходимо найти массив \(p\) любого размера не больше \(2 \cdot 10^4\) такой, что по описанному алгоритму из него получится массив \(t\), или сказать, что это невозможно.

Вам даны три целых числа \(n\), \(k\) и \(f\).

Рассмотрим все бинарные строки (то есть все строки, состоящие из символов \(0\) и/или \(1\)) длины от \(1\) до \(n\). Для каждой такой строки \(s\) вы должны выбрать целое число \(c_s\) от \(0\) до \(k\).

Мультимножество из бинарных строк длины ровно \(n\) считается красивым, если для каждой бинарной строки \(s\) длины от \(1\) до \(n\) выполняется следующее: количество строк в мультимножестве, для которых \(s\) является префиксом, не превосходит \(c_s\).

Например, пусть \(n = 2\), \(c_{0} = 3\), \(c_{00} = 1\), \(c_{01} = 2\), \(c_{1} = 1\), \(c_{10} = 2\) и \(c_{11} = 3\). Мультимножество строк \(\{11, 01, 00, 01\}\) является красивым, так как:

• для строки \(0\) существует \(3\) строки из мультимножества, для которых \(0\) — префикс, и \(3 \le c_0\);
• для строки \(00\) существует одна строка из мультимножества, для которой \(00\) — префикс, и \(1 \le c_{00}\);
• для строки \(01\) существует \(2\) строки из мультимножества, для которых \(01\) — префикс, и \(2 \le c_{01}\);
• для строки \(1\) существует одна строка из мультимножества, для которой \(1\) — префикс, и \(1 \le c_1\);
• для строки \(10\) существует \(0\) строк из мультимножества, для которых \(10\) — префикс, и \(0 \le c_{10}\);
• для строки \(11\) существует одна строка из мультимножества, для которой \(11\) — префикс, и \(1 \le c_{11}\).

А теперь — сама задача. Вы должны посчитать количество способов выбрать числа \(c_s\) для всех бинарных строк \(s\) длины от \(1\) до \(n\) таким образом, чтобы максимальный возможный размер красивого мультимножества был равен ровно \(f\).

Дан двудольный граф с \(n_1\) вершинами в первой доле, \(n_2\) вершинами во второй доле и \(m\) ребрами. Максимальное паросочетание в таком графе — максимальный по размеру набор ребер, такой, что ни одна вершина не инцидентна более чем одному выбранному ребру.

Вам нужно обрабатывать запросы двух видов к этому графу:

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

Обратите внимание, что вы должны решить эту задачу в режиме online. Это означает, что вы не можете считать все входные данные сразу. Вы можете считать каждый запрос только после вывода ответа на последний запрос. Используйте функции fflush в C++ и BufferedWriter.flush в Java после каждого вывода в вашей программе.

В этой задаче вы можете получить вердикт «Решение зависло», так как ее нужно решать в режиме online. Если это случилось, то либо вы не следуете формату вывода, либо нарушаете какое-то из ограничений задачи. Вы можете считать, что это эквивалентно вердикту «Неправильный ответ».

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

Кирилл живёт на связном неориентированном графе из \(n\) вершин и \(m\) рёбер в вершине с номером \(1\). В один прекрасный вечер он собрал у себя \(f\) друзей, \(i\)-й друг живёт в вершине \(h_i\). Таким образом, в настоящий момент все друзья находятся в вершине \(1\), каждый должен добраться домой — \(i\)-й друг должен попасть в вершину \(h_i\).

Вечер подошёл к концу и настала пора расходиться. Оказалось, что у \(k\) (\(k \le 6\)) из его друзей нет машин и им придётся идти пешком, если их никто не подвезёт. Один друг с машиной может подвезти любое количество друзей без машин, но только если он может подвезти их, проехав по одному из кратчайших путей до своего дома.

Например, в графе ниже, друг из вершины \(h_i=5\) может подвезти друзей из следующих наборов вершин: \([2, 3]\), \([2, 4]\), \([2]\), \([3]\), \([4]\), но не может подвезти друга из вершины \(6\) или набор \([3, 4]\).

Вершины в которых живут друзья без машин выделены зелёным, а с машинами — красным.

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

Позиция первого максимума на отрезке \([l; r]\) массива \(x = [x_1, x_2, \ldots, x_n]\) это наименьшее целое число \(i\), такое что \(l \le i \le r\) и \(x_i = \max(x_l, x_{l+1}, \ldots, x_r)\).

Вам дан массив \(a = [a_1, a_2, \ldots, a_n]\) длины \(n\). Найдите количество массивов \(b = [b_1, b_2, \ldots, b_n]\) длины \(n\), удовлетворяющих следующим требованиям:

• \(1 \le b_i \le m\) для всех \(1 \le i \le n\);
• для всех пар \(1 \le l \le r \le n\), позиция первого максимума на отрезке \([l; r]\) массива \(b\) равна позиции первого максимума на отрезке \([l; r]\) массива \(a\).

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

Вам дан граф из \(n\) вершин и \(m\) ориентированных дуг. Дуга под номером \(i\) идет из вершины \(x_i\) в вершину \(y_i\), имеет пропускную способность \(c_i\) и вес \(w_i\). Ни одна дуга не входит в вершину \(1\); также ни одна дуга не выходит из вершины \(n\). В графе нет циклов отрицательного веса (невозможно переместиться из вершины в нее же саму таким образом, что суммарный вес всех ребер, которые мы прошли, будет отрицательным).

Вы должны каждой дуге назначить величину потока (целое число между \(0\) и пропускной способностью дуги, включительно). Для каждой вершины, кроме \(1\) и \(n\), суммарная величина потока на дугах, входящих в нее, должна быть равна суммарной величине потока на дугах, исходящих из нее. Пусть величина потока на \(i\)-й дуге равна \(f_i\), тогда стоимость потока можно вычислить как \(\sum \limits_{i = 1}^{m} f_i w_i\). Вам нужно найти комбинацию величин потока, которая минимизирует стоимость.

Говорите, это баян? Ну, у нас есть дополнительные ограничения на поток по каждой дуге:

• если \(c_i\) — четное число, \(f_i\) тоже должна быть четным числом;
• если \(c_i\) — нечетное число, \(f_i\) тоже должна быть нечетным числом.

Получится ли у вас решить эту задачу?

Даны две перестановки \(a\) и \(b\), обе размера \(n\). Перестановка размера \(n\) — это массив из \(n\) элементов, в который каждое целое число от \(1\) до \(n\) входит ровно один раз. Элементы в каждой перестановке пронумерованы от \(1\) до \(n\).

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

• выбрать целое число \(i\) от \(1\) до \(n\);
• обозначим за \(x\) такое целое число, что \(a_x = i\). Поменять местами \(a_i\) и \(a_x\);
• обозначим за \(y\) такое целое число, что \(b_y = i\). Поменять местами \(b_i\) и \(b_y\).

Вы должны отсортировать обе перестановки в порядке возрастания (то есть должны выполняться условия \(a_1 < a_2 < \dots < a_n\) и \(b_1 < b_2 < \dots < b_n\)) за минимальное количество операций. Обратите внимание, что обе перестановки должны быть отсортированы после того, как вы выполните выбранную вами последовательность операций.

Красные панды приехали в город, чтобы встретиться со своими родственниками, синими пандами! Город представлен в виде числовой оси.

Панды уже запланировали свою встречу, но график постоянно меняется. Вам дано \(q\) обновлений вида x t c.

• Если \(c < 0\), это означает, что дополнительно \(|c|\) красных панд входят на числовую ось в позиции \(x\) и времени \(t\). Затем каждую секунду они могут независимо перемещаться на одну единицу в любом направлении по числовой оси или не перемещаться вовсе.
• Если \(c > 0\), это означает, что дополнительно \(c\) синих панд проверяют позицию \(x\) на наличие красных панд в момент времени \(t\). Если синяя панда не встречает красную панду в этом конкретном месте и времени, она сразу печально покидает числовую ось. Если красная панда есть на позиции в то время, когда синяя панда ее проверяет, они становятся друзьями и покидают числовую ось. Каждая красная панда может стать другом не более чем одной синей панды и наоборот.

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

Движения красных панд могут меняться от обновления к обновлению.

Pak Chanek observes that the carriages of a train is always full on morning departure hours and afternoon departure hours. Therefore, the balance between carriages is needed so that it is not too crowded in only a few carriages.

A train contains \(N\) carriages that are numbered from \(1\) to \(N\) from left to right. Carriage \(i\) initially contains \(A_i\) passengers. All carriages are connected by carriage doors, namely for each \(i\) (\(1\leq i\leq N-1\)), carriage \(i\) and carriage \(i+1\) are connected by a two-way door.

Each passenger can move between carriages, but train regulation regulates that for each \(i\), a passenger that starts from carriage \(i\) cannot go through more than \(D_i\) doors.

Define \(Z\) as the most number of passengers in one same carriage after moving. Pak Chanek asks, what is the minimum possible value of \(Z\)?

Вам дана матрица \(a\), состоящая из \(n\) строк и \(m\) столбцов. Каждый элемент матрицы равен \(0\) или \(1\).

Вы можете выполнять следующую операцию любое количество раз (возможно, ни одного): выбрать элемент матрицы и заменить его на \(0\) или \(1\).

Также вам даны два массива \(A\) и \(B\) (длиной \(n\) и \(m\) соответственно). После выполнения операций матрица должна удовлетворять следующим условиям:

1. количество единиц в \(i\)-й строке матрицы должно быть ровно \(A_i\) для каждого \(i \in [1, n]\).
2. количество единиц в \(j\)-м столбце матрицы должно быть ровно \(B_j\) для каждого \(j \in [1, m]\).

Вычислите минимальное количество операций, которое вам нужно выполнить.

У Владислава есть сын, который очень хотел поступить в МИТ. Общежитие колледжа в МИТ (Молдавский институт технологий) можно представить в виде дерева с \(n\) вершинами, где каждая вершина представляет собой комнату с ровно одним студентом. Дерево — это связный неориентированный граф с \(n\) вершинами и \(n-1\) ребром.

Сегодня ночью есть три типа студентов:

• студенты, которые хотят веселиться и слушать музыку (обозначены \(\texttt{P}\)),
• студенты, которые хотят спать и наслаждаться тишиной (обозначены \(\texttt{S}\)), и
• студенты, которым не важно, что делать ночью (обозначены \(\texttt{C}\)).

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

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

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

Вам дан неориентированный связный простой граф с \(n\) вершинами и \(m\) ребрами, где ребро \(i\) соединяет вершины \(u_i\) и \(v_i\). С каждым ребром связаны два положительных параметра \(a_i\) и \(b_i\). Кроме того, вам дано целое число \(k\).

Неотрицательный массив \(x\) длины \(m\) называется генератором \(k\)-остовного-дерева, если он удовлетворяет следующим условиям:

• Рассмотрим неориентированный мультиграф с \(n\) вершинами, в котором ребро \(i\) клонировано \(x_i\) раз (т.е. существует \(x_i\) ребер, соединяющих \(u_i\) и \(v_i\)). Можно разбить ребра этого графа на \(k\) остовных деревьев, где каждое ребро принадлежит ровно одному остовному дереву\(^\dagger\).

Стоимость такого массива \(x\) определяется как \(\sum_{i = 1}^m a_i x_i^2 + b_i x_i\). Найдите минимальную стоимость генератора \(k\)-остовного-дерева.

\(^\dagger\) Остовное дерево (мульти)графа — это подмножество ребер графа, которые образуют дерево, соединяющее все вершины графа.

Вас попросили организовать очень важную конференцию об искусстве. Первый шаг — выбрать даты.

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

Вы опросили \(n\) потенциальных лекторов по поводу их доступности. Лектор \(i\) указал, что сможет выступить в любой день с \(l_i\) по \(r_i\) включительно.

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

Для каждого \(k\) от \(1\) до \(n\) найдите, сколько есть способов выбрать отрезок из \(k\) подряд идущих дней в качестве дат конференции.

Монокарп собирает армию в компьютерной игре, чтобы сразиться с драконом.

Армия состоит из двух частей: героев и защитных артефактов. У каждого героя один параметр — его здоровье. У каждого защитного артефакта тоже один параметр — его прочность.

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

Бой состоит из раундов, которые проходят следующим образом:

• сначала дракон наносит каждому герою урон, равный \(\frac{1}{a + b}\) (вещественное число без округления), где \(a\) — количество живых героев, а \(b\) — количество активных артефактов;
• после этого все герои со здоровьем \(0\) или меньше умирают;
• наконец, некоторые артефакты деактивируются. Артефакт с прочностью \(x\) деактивируется, когда происходит одно из следующего: герой, держащий артефакт, либо умирает, либо получает суммарно \(x\) урона (от начала боя). Если артефакт не выдан ни одному из героев, он считается неактивным с самого начала битвы.

Бой заканчивается, если в живых не осталось ни одного героя.

Изначально армия пуста. Приходит \(q\) запросов: добавить в армию героя со здоровьем \(x\) или артефакт с прочностью \(y\). После каждого запроса найдите максимальное количество раундов, которые Монокарп может продержаться, если оптимально распределит артефакты.

Кевин недавно узнал определение дисперсии. Для массива \(a\) длины \(n\) дисперсия \(a\) определяется следующим образом:

• Пусть \(x=\dfrac{1}{n}\displaystyle\sum_{i=1}^n a_i\), т.е. \(x\) — это среднее арифметическое массива \(a\);
• Тогда дисперсия \(a\) равна \(\) V(a)=\frac{1}{n}\sum_{i=1}^n(a_i-x)^2. \(\)

Теперь Кевин даст вам массив \(a\), состоящий из \(n\) целых чисел, а также целое число \(k\). Вы можете выполнять следующую операцию над \(a\):

• Выберите отрезок \([l,r]\) (\(1\le l\le r\le n\)), затем для каждого \(l\le i\le r\) увеличьте \(a_i\) на \(k\).

Для каждого \(1\le p\le m\) вам нужно найти минимально возможную дисперсию \(a\) после выполнения ровно \(p\) операций, независимо для каждого \(p\).

Для простоты вам нужно только вывести ответы, домноженные на \(n^2\). Можно доказать, что результаты всегда являются целыми числами.