Майлз опять сбегает от Мигеля О'Хары, но в этот раз он смог захватить с собой устройство для перемещения между двумя мирами. К сожалению, его перемещения ограничены одним городом в каждом из миров. Но эти два города очень похожи: в каждом из них ровно $$$n$$$ небоскребов, располагающихся в одних и тех же точках пространства.

Некоторые пары небоскребов, расположенных в одном мире, пригодны для того, чтобы протянуть между ними паутину и переместиться с одного на другой (в любом из двух направлений). В первом мире есть ровно $$$m_1$$$ таких пар небоскребов, а во втором — ровно $$$m_2$$$. Известно, за какое время можно переместиться между доступными парами небоскребов в каждом мире. Помимо этого Майлз может, находясь на $$$i$$$-м небоскребе в первом мире, переместиться на $$$i$$$-й небоскреб во втором, и наоборот, за $$$x$$$ секунд.

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

Вы вступили на сторону зла и теперь работаете на «Alchemax»!.

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

Ученые выяснили, что для успеха операции:

1. сначала надо заранее заготовить некоторое количество порций корма $$$m$$$, после чего отдать одну порцию этого корма в лабораторию на анализ;
2. затем поровну распределить оставшиеся $$$m - 1$$$ порций корма между пауками (каждый паук при этом должен получить целое число порций корма);
3. в конце корма не должно остаться, так как его утилизация привлечет ненужное внимание.

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

Ловля пауков не всегда проходит удачно, поэтому вам известно только что после сегодняшней операции в лаборатории появится от $$$1$$$ до $$$k$$$ пауков. Определите максимальное количество корма, не превышающее $$$n$$$, чтобы при любом количестве пойманных сегодня пауков, вы могли отдать одну порцию в лабораторию, а оставшиеся распределить между пауками поровну. Разрешается не кормить пауков вообще (но только если не кормить ни одного из них).

Для путешествий между вселенными в Паучьих мирах существуют специальные порталы. Сеть из $$$m$$$ порталов для $$$n$$$ вселенных представляет из себя граф из $$$n$$$ вершин и $$$m$$$ ребер. Каждый портал связывает какие-то две вселенные, причем никакие два портала не связывают одну и ту же пару вселенных.

Для перемещения Мигель О'Хара использует свои высокотехнологичные портальные часы. Но самые первые версии этих часов были не настолько развиты, и не позволяли сразу путешествовать в произвольные вселенные. А именно, у часов был параметр энергетического уровня, который изначально был равен $$$0$$$.

Каждый портал характеризуется некоторой характеристикой $$$w$$$ — минимальным значением энергетического уровня, необходимым для использования этого портала. Если значение энергетического уровня часов меньше $$$w$$$, то воспользоваться этим порталом сейчас нельзя. К счастью, есть способ увеличить энергетический уровень: при первом попадании во вселенную $$$i$$$ энергетический уровень часов навсегда увеличивается на $$$a_i$$$.

Мигель задумался, какое максимальное значение энергетического уровня он может получить на старом прототипе часов, если посетит все вселенные, в которые сможет попасть, начав свой путь из вселенной номер $$$s$$$? Помогите ему ответить на этот вопрос.

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

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

Правила теста очень простые: вам дается целое положительное число $$$n$$$, после чего вы должны назвать строку $$$s$$$ из строчных латинских букв от 'a' до 'z' длины ровно $$$n$$$. Как только вы назвали эту строку, машина выполняет следующие действия:

1. Сначала вычисляется количество уникальных букв в строке $$$s$$$, обозначим его за $$$k$$$.
2. Затем каждой использованной в $$$s$$$ букве алфавита сопоставляется «вес» — уникальное целое число от $$$1$$$ до $$$k$$$. Обозначим этот «вес» буквы $$$c$$$ за $$$w(c)$$$.
3. После чего вычисляется следующая величина: $$$T = \sum\limits_{c \in s} w(c)$$$, иными словами — суммируются веса всех букв в названной строке.

Разумеется, машина назначает веса буквам так, чтобы итоговая сумма получилась как можно меньше. Например, если вы назвали строку «aba», то машина назначит вес $$$1$$$ букве 'a' и вес $$$2$$$ букве 'b', после чего конечное значение получится равным $$$1 + 2 + 1 = 4$$$.

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

Мало кто знает, но в Лего-вселенной есть свой суперзлодей по кличке Пятно. Только он не настолько известный, потому что он может создавать не красивые овальные «дыры» в ткани реальности, а только скучные прямоугольные.

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

Сейчас у него уже есть $$$n$$$ прямоугольниых «дыр», расположенных в одной плоскости. Их стороны параллельны осям координат, и эти «дыры» можно

• перемещать и накладывать друг на друга;
• поворачивать на $$$90^\circ$$$ в рамках их общей плоскости (то есть менять местами их высоту и ширину).

Определите, какую максимальную по количеству «дыр» последовательность можно составить, чтобы каждая следующая «дыра» была вложена в предыдущую. Мы считаем, что «дыру» размера $$$(h_1, w_1)$$$ можно вложить в «дыру» размера $$$(h_2, w_2)$$$, если $$$h_1 \le h_2$$$ и $$$w_1 \le w_2$$$.

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

Игра начинается с прямоугольника размера $$$n \times m$$$ и проходит следующим образом:

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

Всего Гвен и алгоритм в часах совершают по $$$k$$$ ходов, т.е. общее количество ходов равно $$$2k$$$. И Гвен, и компьютер всегда делают свои ходы оптимально.

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

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

Поэтому он решил потренироваться на черно-белой версии кубика Рубика, при чем еще и двумерной, а не трехмерной. Для этого он взял клетчатую табличку размера $$$n \times m$$$, каждая клетка которого закрашена либо в черный, либо в белый цвет. Как и в кубике Рубика, цвета элементов можно менять, но вместо вращения с этой таблицей можно делать одну из двух операций:

• инвертировать все цвета в любом столбце;
• инвертировать все цвета в любой строке.

Конечная цель — добиться того, чтобы существовал «путь» по черным клеткам из левого верхнего угла таблицы в правый нижний с шагами на один вправо и шагами на один вниз. Иными словами, должна существовать такая последовательность черных клеток $$$(r_1, c_1), (r_2, c_2), \ldots, (r_{n+m-1}, c_{n+m-1})$$$, что

• $$$(r_1, c_1)$$$ равно $$$(1, 1)$$$, то есть левой верхней клетке;
• $$$(r_{n+m-1}, c_{n+m-1})$$$ равно $$$(n, m)$$$, то есть правой нижней клетке;
• и для любых двух соседних в этой последовательности клеток $$$(r_i, c_i)$$$ и $$$(r_{i+1}, c_{i+1})$$$ либо $$$r_i = r_{i+1}$$$ и $$$c_{i+1} = c_i + 1$$$, либо, наоборот, $$$c_i = c_{i+1}$$$ и $$$r_{i+1} = r_i + 1$$$.

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

Квантовые дыры, разрушающие вселенные, иногда можно «залатать», тем самым остановив разрушение мира. Но это удается далеко не всегда.

Мигель придумал способ оценивать опасность квантовой дыры целым числом. Для этого сначала информация о квантовой дыре представляется в виде битовой строки длины ровно $$$n$$$. Каждая ее подстрока $$$t$$$ (последовательность подряд идущих бит) длины $$$k$$$ вносит свой независимый вклад $$$\mathtt{danger}(t) = d_t$$$ в суммарную опасность дыры, а именно: $$$$$$\mathtt{danger}(s) = \sum\limits_{i=1}^{n-k+1} \mathtt{danger}(s_{i,\ldots,i+k-1}) \text{,}$$$$$$ где $$$s_{i,\ldots,i+k-1}$$$ означает подстроку $$$s$$$ длины $$$k$$$ с началом в $$$i$$$-м бите.

Значения опасности всех двоичных строк длины $$$k$$$ уже изучены и известны, всего таких значений $$$2^k$$$. Например, для $$$k = 2$$$ вам известны $$$4$$$ значения: $$$d_{\mathtt{00}}$$$, $$$d_{\mathtt{01}}$$$, $$$d_{\mathtt{10}}$$$, $$$d_{\mathtt{11}}$$$.

Сегодня Марго Кесс от скуки пришла в голову идея найти описание самой безопасной квантовой дыры. Найдите битовую строку длины ровно $$$n$$$, опасность которой минимальна.

Аномалии очень опасны тем, что могут изменять естественный ход событий, и даже вмешиваться в ключевые события, что может повлечь за собой необратимые последствия для многих вселенных. После того, как Пятно появился на Земле-2099, он нарушил столько ключевых событий, что аж $$$n$$$ соседних вселенных под угрозой: паутина мультивселенной расплетается. И вам предстоит это исправить!

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

1. некоторые пары вселенных связаны односторонними энергетическими каналами;
2. из каждой из $$$n$$$ вселенных выходят ровно два канала;
3. в каждую из $$$n$$$ вселенных ведут ровно два канала;
4. каждый канал характеризуется парой чисел $$$a$$$ и $$$b$$$, которые означают, что мощность энергии, пущенной по этому каналу, должна лежать между $$$a$$$ и $$$b$$$ включительно.

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

При этом мощность энергии, пускаемой по каждому выбранному каналу, должна быть одинакова (даже если каналы находятся на разных циклах). Более формально, должно существовать такое значение мощности $$$w$$$, что на каждом выбранном канале $$$a_i \le w \le b_i$$$.

Определите, можно ли выбрать такие каналы, и такое значение мощности, чтобы все требуемые условия были выполнены. Спасите мультивселенную!

Несколько Пауков пытаются остановить обрушение «Alchemax», но Пятно им мешает. Действительно, чем больше хаоса, тем проще ему будет скрыться, ведь Гвен, Майлз, Хоби и Павитр будут заняты спасением окружающих людей.

Чтобы представить себе ситуацию получше, рассмотрим вид сверху, и скажем, что Пауки располагаются на плоскости в точке с координатами $$$(0, 0)$$$ — прямо в сердце «Alchemax», а стены здания «Alchemax» представляют из себя окружность радиуса $$$10^6$$$ с центром в той же точке $$$(0, 0)$$$.

Для того, чтобы стены «Alchemax» после очередного запуска коллайдера не обрушились наружу, Пауки используют для ее сдерживания новый вид паутины: непрерывную паутину. Она распространяется из точки $$$(0, 0)$$$ как свет — в каждом направлении на произвольно далекое расстояние. И чтобы помешать им, Пятно расположил $$$n$$$ своих «дыр в пространстве» вокруг. Каждая дыра — это «абсолютно черный» круглый объект, то есть каждая такая дыра полностью поглащает все, что на в нее попадает.

Другими словами, из точки $$$(0, 0)$$$ во все стороны выходят лучи паутины, но если на пути луча встречается дыра в пространстве, дальше нее луч не пойдет. Ваша задача — определить, до какой части окружности стен «Alchemax» паутина все же дотянется.

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

Всего в сообществе $$$n$$$ Пауков, и его иерархия представляет собой подвешенное дерево. Корнь этого дерева — паук под номером $$$1$$$, Мигель О'Хара. Сама иерархия задается $$$n - 1$$$ связями непосредственного подчинения между членами сообщества. Будем говорить, что Паук номер $$$u$$$ — «ментор» Паука $$$v$$$, если между ними есть связь непосредственного подчинения, и $$$u$$$ располагается в иерархии ближе к Мигелю, чем $$$v$$$. В таком случае будем называть $$$v$$$ «подчиненным» $$$u$$$.

После появления Майлза в сообществе, и его побега, члены сообщества разделились на две группы, у каждой из которых свое понимание того, как им следует действовать дальше. Назовем эти два имеющихся мнения A и B. Беспорядком в сообществе назовем количество таких пар $$$u$$$ и $$$v$$$, что Паук номер $$$u$$$ — ментор Паука номер $$$v$$$ (а $$$v$$$, соответственно — подчиненный $$$u$$$), и при этом у Паука номер $$$u$$$ мнение A, а у паука номер $$$v$$$ мнение B.

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

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

Майлз продолжает бороться с «Alchemax». Его задача в этот раз — взломать настройки коллайдера, чтобы остановить его повторный запуск.

Всего у коллайдера есть $$$n$$$ настроек $$$a_i$$$ с номерами от $$$1$$$ до $$$n$$$, каждая из них является целым положительным числом. Компания предусмотрела защиту настроек от посторонних, поэтому узнать значение определенной настройки напрямую нельзя. Однако любой человек может запросить некоторое $$$f(x)$$$, равное значению настройки с номером, циклически сдвинутым от $$$x$$$ на $$$c$$$ вперед ($$$0 \le c \le n - 1$$$), то есть с номером $$$x + c$$$, если $$$x + c \le n$$$, и $$$x + c - n + 1$$$ иначе.

Майлз выяснил, что на самом деле настройки идут по возрастанию, то есть что $$$a_{i + 1} \gt a_i$$$ для всех $$$i$$$ от $$$1$$$ до $$$n - 1$$$. Теперь для остановки коллайдера Майлзу обязательно нужно найти известное только сотрудникам «Alchemax» число $$$c$$$ — сдвиг в номерах, используемый в системе доступа к настройкам.

Узнайте значение $$$c$$$, если вам дано число $$$n$$$ и возможность запрашивать значения $$$f(x)$$$ не больше $$$42$$$ раз.

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

Вы можете не более $$$42$$$ раз запросить значение $$$f(x)$$$ для $$$1 \le x \le n$$$. Чтобы запросить очередное значение, выведите на отдельной строке «? $$$x$$$», где вместо $$$x$$$ укажите нужное число. Если вы не превысили лимит в $$$42$$$ запроса вида «?», в следующей строке интерактор выведет единственное целое число $$$f(x)$$$, равное $$$a_{x+c}$$$ при $$$x + c \le n$$$ или $$$a_{x+c-n+1}$$$ иначе.

Для того, чтобы вывести ответ на задачу, напечатайте «! $$$c$$$», где вместо $$$c$$$ должно быть значение сдвига ($$$0 \le c \le n - 1$$$). Вывод ответа не учитывается в количестве запросов. После вывода ответа ваша программа должна завершиться с нулевым кодом возврата.

Если в какой-то момент ваша программа превышает лимит в $$$42$$$ запроса, интерактор выведет на следующей строке $$$-1$$$ и завершится с вердиктом WA (Wrong Answer). Во избежание получения вердиктов RE, TL или IL, прочитав ответ $$$-1$$$, ваша программа должна завершиться с нулевым кодом возврата.

Не забывайте после каждого запроса сбрасывать буфер вывода, чтобы интерактор получил ваш запрос. Это можно сделать с помощью std::cout.flush() в C++, System.out.flush() в Java и sys.stdout.flush() в Python, а также аналогичными командами в других языках. Если ваша программа не сбрасывает буфер вывода, она получит вердикт TL или IL.