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

Место, где живут тёмные эльфы, представляет собой пещеру, в которой есть $$$n$$$ помещений, пронумерованных от $$$1$$$ до $$$n$$$, соединенных $$$n - 1$$$ узким проходом. Причем, из любого помещения по проходам достижимо любое другое. В каждом помещении живёт ровно один тёмный эльф, а в проходах не живёт никто. В $$$i$$$-м помещении живёт эльф номер $$$i$$$. У каждого эльфа есть значение $$$w_i$$$ — его сила в бою.

Малефисента собирается в замок королевы Ингрит. Совет тёмных эльфов решил отправить вместе с ней группу эльфов, такую что в ней будет хотя бы два эльфа, и помещения, в которых живут эльфы, входящие в группу, образуют связную область. Иными словами, для любых двух эльфов $$$a$$$ и $$$b$$$, входящих в группу, все эльфы, живущие в помещениях на простом пути между помещениями $$$a$$$ и $$$b$$$, также должны входить в группу. Разумеется, Малефисенту должен сопровождать наиболее сильный отряд, поэтому совет хочет выбрать такую группу, чтобы среднее арифметическое силы участников группы было максимально. Помогите совету найти это значение.

Малефисента попала в магическую ловушку — круг, на границе которого расположено $$$n$$$ свечек, пронумерованных от $$$1$$$ до $$$n$$$ в порядке обхода. Каждая свечка горит красным, жёлтым или синим пламенем, $$$i$$$-я свечка горит цветом $$$s_i$$$. К счастью, Малефисента умеет выбираться из таких ловушек — для этого нужно сделать так, чтобы $$$i$$$-я свечка горела цветом $$$t_i$$$. После этого из круга можно будет просто выйти.

Малефисента может выбрать любую свечку, соседи которой горят разным цветом, и поменять цвет её пламени на произвольный. На это действие потребуется одна единица магической силы. У Малефисенты осталось всего $$$10 \cdot n$$$ единиц магической силы. Помогите ей найти последовательность действий, которая поможет выбраться из ловушки, либо скажите, что это невозможно.

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

Заклятье описывается двумы натуральными числами $$$a$$$ и $$$b$$$. Процесс снятия заклятья происходит следующим образом:

1. Перемножить числа от $$$a$$$ до $$$b$$$ включительно
2. Взять сумму цифр полученного числа
3. Если результат не меньше $$$10$$$, вернуться к пункту $$$2$$$

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

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

Стена имеет огромную высоту и бесконечно простирается вдоль прямой. Введём на ней числовую ось. Всего есть $$$n$$$ лесорубов, пронумерованных от $$$1$$$ до $$$n$$$. Лесорубы очень ленивые, и рубят стену лишь для того, чтобы заработать. Поэтому, если нанять $$$i$$$-го лесоруба, он уменьшит высоту стены на отрезке от координаты $$$l_i$$$ до координаты $$$r_i$$$ лишь на полметра. И при этом, каждый лесоруб может быть нанят не более одного раза.

Стефан понял, что он не сможет прорубить стену. Однако, ему стало интересно, сколькими способами он может выбрать два целых числа $$$a$$$ и $$$b$$$ ($$$1 \le a \le b \le n$$$), что если нанять всех лесорубов с номерами от $$$a$$$ до $$$b$$$ и только их, высота стены всюду изменится на целое число метров. Обратите внимание, что нулевое изменение высоты также считается изменением на целое число метров.

У Авроры есть $$$n$$$ кубиков. У каждого кубика есть шесть сторон, на каждой из которых написана цифра от $$$0$$$ до $$$9$$$. Цифры на одном кубике могут повторяться.

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

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

Аврора и Нотграсс решили сыграть в теннис и попросили Флитл побыть судьёй. Изначально их счет равнялся $$$0 : 0$$$. Затем, несколько раз очки одного из игроков увеличивались на $$$1$$$. А закончилась игра со счётом $$$a : b$$$.

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

• $$$0 : 0$$$
• $$$1 : 0$$$, $$$\textrm{НОД}(1, 0) = 1$$$
• $$$2 : 0$$$, $$$\textrm{НОД}(2, 0) = 2$$$
• $$$2 : 1$$$, $$$\textrm{НОД}(2, 1) = 1$$$
• $$$2 : 2$$$, $$$\textrm{НОД}(2, 2) = 2$$$
• $$$2 : 3$$$, $$$\textrm{НОД}(2, 3) = 1$$$

В таком случае, у Фислвит получилась бы сумма $$$1 + 2 + 1 + 2 + 1 = 7$$$.

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

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

Исходно на свадьбе находится $$$n$$$ фей, Аврора пронумеровала их от $$$1$$$ до $$$n$$$. Фея номер $$$i$$$ характеризуется своей общительностью — целым неотрицательным числом $$$a_i$$$.

За время наблюдения, Аврора видела $$$q$$$ интересных моментов. Во время $$$j$$$-го из них происходило событие одного из трех типов:

1. На свадьбу приходит фея с общительностью $$$v_j$$$. Аврора назначает ей первый неиспользованный ранее номер. Например, первая пришедшая фея получит номер $$$n + 1$$$, следующая — $$$n + 2$$$ и так далее.
2. Фея с номером $$$p_j$$$ покидает свадьбу.
3. На свадьбе объявляется танец, характеризующийся своей экспрессивностью $$$e_j$$$ — целым неотрицательным числом. После танца, общительности всех фей изменяются. Если до танца фея имела общительность $$$b$$$, то после ее общительность станет равна $$$b \oplus e_j$$$, то есть побитовому исключающему ИЛИ чисел $$$b$$$ и $$$e_j$$$.

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

Малефисента практикуется в создании защитного барьера для Топких Болот. Процесс создания барьера состоит из произнесения $$$n$$$ заклинаний. Пусть $$$i$$$-е произнесённое заклинание имеет силу $$$s_i$$$. Тогда прочность барьера будет равна:

$$$$$$\sum_{i = 1}^{q} \max_{j = l_i}^{r_i} s_j$$$$$$

Где $$$1 \le l_i \le r_i \le n$$$ для любого $$$1 \le i \le q$$$.

Малефисента попробует построить барьер $$$m$$$ раз, причем в $$$i$$$-й раз она планирует произнести заклинания с силами $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$$$. Но она пока что не определилась с порядком произнесения заклинаний для каждой попытки. Помогите ей определить максимальную прочность барьера, которой она может добиться, в каждой из попыток.

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

Каждое заклятье можно представить в виде неотрицательного целого числа. Скажем, что $$$i$$$-му заклятью соответствует число $$$a_i$$$. Тогда, чтобы снять все заклятья сразу, надо найти число $$$$$$\sum\limits_{1 \le i \lt j \lt k \le n} a_i \cdot a_j \cdot a_k$$$$$$

Помогите ей поскорее разобраться с этой проблемой. Посчитайте число, необходимое для снятия всех заклятий. Поскольку число может получиться слишком большим, требуется посчитать его по модулю $$$1\,000\,000\,007$$$.

Развлекаясь с ранее неизведанными заклинаниями, Малефисента случайно получила свиток с посланием из будущего. На свитке было написано какое-то занимательное заклинание.

<note>
<to></to>
<from></from>
<heading></heading>
<body></body>
</note>

Малефисента сразу заметила несколько закономерностей. А именно: заклинание представляет из себя правильную скобочную последовательность, в которой открывающаяся скобка соответствует шаблону «<S>», а парная ей закрывающаяся — шаблону «</S>», где строка S — непустая строка из строчных латинских букв, равная для парных скобок.

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