Саша уже не помнил, сколько времени бродил среди жёлтых стен и гудящих ламп. Чем дальше он заходил в Закулисье, тем больше терял рассудок. Он снова и снова возвращался в одни и те же комнаты и наконец решил составить карту лабиринта.

На карте он обозначил комнаты вершинами, а двусторонние переходы — рёбрами. Получился связный неориентированный граф. С удивлением Саша заметил, что каждое ребро принадлежит не более чем одному вершинно простому циклу (иначе говоря, граф является реберным кактусом).

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

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

Бродя по бесконечным желтым коридорам Закулисья, вы нашли $$$n$$$ банок с миндальной водой весом $$$a_1, a_2, \ldots, a_n$$$.

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

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

Двое странников выпали из реальности в Закулисье (Backrooms), уровни которого пронумерованы неотрицательными целыми числами. Сначала они только поднимались по уровням, потом в один и тот же час оказались на одном уровне и дальше только спускались. Номер своего уровня в Закулисье узнать нельзя, поэтому каждый час странники записывали в журнал лишь, на сколько уровней первый выше второго.

Более формально, массив неотрицательных целых чисел $$$h_1, h_2, \ldots, h_m$$$ называется горой с вершиной $$$k$$$, если $$$h_1 \le h_2 \le \ldots \le h_k \ge h_{k+1} \ge \ldots \ge h_m$$$. Пусть поход длился $$$m$$$ часов и в $$$i$$$-й час первый странник был на уровне $$$a_i$$$, а второй — на уровне $$$b_i$$$. Тогда $$$a$$$ и $$$b$$$ — горы с одной и той же вершиной $$$k$$$, $$$a_k = b_k$$$, а в журнал записаны числа $$$d_i = a_i - b_i$$$ при $$$i = 1, \ldots, m$$$.

В руки исследователей Закулисья попал журнал из $$$n$$$ записей $$$c_1, c_2, \ldots, c_n$$$, но какие из них относятся к походу, неизвестно. У исследователей есть $$$q$$$ независимых гипотез: каждая задаётся числами $$$l$$$ и $$$r$$$ и означает, что поход длился $$$m = r - l + 1$$$ часов и $$$d_i = c_{l+i-1}$$$. Для каждой гипотезы определите, могла ли она быть верной, и если могла — на каком наименьшем уровне странники могли встретиться.

Вы исследуете Закулисье и сейчас застряли в одной очень странной аномалии. После кропотливых исследований вы поняли, что тут недавно прошёл командный контест ICPC формата.

Вам удалось выяснить, что в контесте участвовали $$$n$$$ команд и было $$$m$$$ задач. Также сохранился журнал всех посылок команд в хронологическом порядке, однако вердикты не сохранились. Посылка с вердиктом «принято» означает, что команда решила соответствующую задачу. После этого команда могла продолжать отправлять посылки по той же задаче, но они уже ни на что не влияли. Известно, что команда $$$i$$$ решила ровно $$$p_i$$$ различных задач.

За каждую задачу команда, решившая её первой, получает одну звёздочку (aka first-to-solve). Задача, которую никто не решил, не приносит звёздочку никому.

Для выхода из аномалии вам осталось ответить на один очень странный вопрос: какое минимальное количество звёздочек могла получить команда номер $$$1$$$?

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

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

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

Когда топот стих, вы заглянули в комнату и обнаружили ровно $$$n$$$ клеток со следами (никакого животного, естественно, уже не было).

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

В Закулисье обитают натюрморты (Still Lifes) — странные существа, похожие на людей. Каждый шаг даётся им с трудом, поэтому они стараются ходить как можно меньше. Зато в этом странном месте они умеют телепортироваться, меняясь друг с другом местами.

В одном из коридоров находятся $$$n$$$ натюрмортов. Коридор можно считать числовой прямой. Натюрморт с номером $$$i$$$ находится в точке $$$s_i$$$ и хочет оказаться в точке $$$t_i$$$.

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

• поменять местами любых двух натюрмортов с помощью телепортации, не делая шагов;
• передвинуть любого натюрморта на единицу влево или вправо, сделав один шаг.

В одной точке могут находиться несколько натюрмортов. Найдите минимальное суммарное число шагов, необходимое, чтобы каждый натюрморт $$$i$$$ оказался в точке $$$t_i$$$.

Как известно, с освещением в Закулисье бывает беда. Мало того, что электричество идёт мимо счётчика, так ещё и лампы периодически мигают.

Даня знает, что они мигают по строго определённому алгоритму: для первых $$$n$$$ мерцаний продолжительность $$$i$$$-го мерцания составляет от $$$a_i$$$ до $$$b_i$$$ секунд включительно, а начиная с $$$(n+1)$$$-го мерцания каждое мерцание длится дольше предыдущего на величину от $$$x$$$ до $$$y$$$ секунд включительно: например, $$$(n+1)$$$-е мерцание может длиться от $$$a_n+x$$$ до $$$b_n+y$$$ секунд включительно. Также для любого $$$1 \lt i \leq n$$$ верно, что $$$a_i \ge a_{i - 1}$$$ и $$$b_i \ge b_{i - 1}$$$.

Последнее мерцание, которое увидел Даня, продолжалось ровно $$$t$$$ секунд, после чего он задался вопросом: какое по счёту оно может быть? Если никакое мерцание не могло продолжаться $$$t$$$ секунд, выведите $$$0$$$.

Вы застряли в Закулисье регулярности — измерении, напоминающем обычное Закулисье, но подчиняющемся своим особым правилам. К счастью, вам повезло, и вам попался блокнот с описанием того, как проходить различные комнаты, и планом побега.

Всего существует $$$n$$$ типов комнат. Для каждого типа известно, сколько минут занимает прохождение этой комнаты. План побега — это строка. Каждая из первых $$$n$$$ заглавных букв латинского алфавита обозначает комнату и сама по себе является корректным планом побега. Пусть $$$s$$$, $$$f$$$ — корректные планы побега, тогда:

• $$$s f$$$ — корректный план побега, это означает, что надо пройти план $$$s$$$, затем $$$f$$$.
• $$$s \, | \, f$$$ — корректный план побега, это означает, что надо пройти ровно один из планов $$$s$$$, $$$f$$$, причём альтернатив может быть сколь угодно много. У $$$|$$$ приоритет меньше, чем у конкатенации (предыдущего правила).
• $$$(s)$$$ — корректный план побега, это означает, что надо пройти $$$s$$$ один раз. (Скобки служат той же цели, что и в математических выражениях).
• $$$(s)x$$$ — после скобок может идти число $$$x$$$ от 2 до 9 включительно, это означает, что нужно пройти план $$$s$$$ ровно $$$x$$$ раз, причём не обязательно все разы одинаково.

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

Человек, попавший в Закулисье, имеет шансы на каждом шагу столкнуться с аномалиями. Например, Паша, провалившись в Закулисье во время перехода из одного корпуса ИТМО в другой, наблюдал следующую картину: в кругу друг напротив друга стояли $$$n$$$ пиратов и играли в камень-ножницы-бумагу.

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

Паша задумался — а сколько вообще существует вариантов осмысленного раунда в такой игре? Помогите ему и ответьте на этот вопрос. Так как это число может быть очень большим, его нужно выводить по модулю $$$10^9 + 7$$$.

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

Представим уровень как двухмерную плоскость. Обозначим координаты $$$i$$$-го маячка как позицию в точке $$$(x_i, y_i)$$$. Как оказалось, они автоматически устанавливают соединения друг с другом. Два маячка $$$i$$$ и $$$j$$$ устанавливают соединение друг с другом тогда и только тогда, когда $$$|x_i-x_j| = |y_i-y_j| = k$$$. Между каждой парой маячков существует ровно один сигнал, который изображается отрезком между соответствующими точками.

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

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

Вы оказались в Закулисье — бесконечном лабиринте пустых комнат с жёлтыми стенами и мерцающими лампами.

Однако в этот раз лабиринт оказался необычным. Всего в нём $$$n$$$ комнат, соединённых $$$n-1$$$ коридорами так, что из любой комнаты можно добраться до любой другой ровно одним способом (другими словами, лабиринт является деревом).

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

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

Вам предстоит провести в Закулисье $$$n$$$ минут. Определите, на сколько изолированных частей распадётся лабиринт после каждой перестройки.

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

Вам дан массив $$$a$$$ из $$$n$$$ целых чисел. Машина умеет выполнять только одну операцию:

Выбрать два различных индекса $$$i$$$ и $$$j$$$ ($$$1 \le i, j \le n$$$, $$$i \ne j$$$) и заменить $$$a_i$$$ на $$$a_i \oplus a_j$$$, где $$$\oplus$$$ обозначает побитовое исключающее ИЛИ (XOR).

Ваша задача — определить, можно ли отсортировать массив по неубыванию, используя не более $$$4n$$$ операций. Если это возможно, выведите любую подходящую последовательность операций. Заметьте, что необязательно сохранять исходные элементы массива, то есть достаточно получить любой отсортированный массив с помощью описанной операции.