BThero живет в богатой прекрасной стране — Демиляндии. Демиляндия представляет собой сеть из $$$n$$$ городов и $$$n-1$$$ двусторонних дорог между ними. Гарантируется, что из любого города можно попасть в любой другой по этим дорогам.

BThero учится в университете на программиста. Первый курс для него закончился успешно, теперь он хочет летом подработать немного денег. Он смог подсчитать для каждого города значение $$$p_i$$$ — сколько долларов он сможет заработать в $$$i$$$-м городе. Получилось так, что массив $$$p$$$ состоит из различных целых чисел от $$$1$$$ до $$$n$$$.

BThero еще не бывал в большинстве городов своей страны. Поэтому он решил убить двух зайцев одним выстрелом — он выберет себе маршрут, который начинается в произвольном городе $$$a$$$, заканчивается в произвольном городе $$$b \gt a$$$ и не проходит через один город дважды. По пути он будет одновременно подрабатывать в городах.

Однако ситуация с программистами в стране не очень простая. В некоторых городах он может легко заработать крупную сумму денег, а в некоторых ему придется экономить на расходах. От этого напрямую зависит его настроение. Если в городе непосредственно до нынешнего он заработал $$$x$$$ денег, а в нынешнем заработает $$$y \lt x$$$, то его настроение будет плохим. Соответственно, если $$$y \gt x$$$, его настроение будет хорошим.

Назовем запоминающимся маршрут, вдоль которого у BThero настроение будет изменяться каждый раз. Примеры его доходов в запоминающихся маршрутах: $$$[2, 5, 1, 4]$$$, $$$[3, 1, 2]$$$, $$$[1, 2]$$$. Заметим, что маршруты из двух городов тоже являются запоминающимися.

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

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

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

Учитель знает что в быту есть шарики всего $$$m$$$ цветов, пронумерованных от $$$1$$$ до $$$m$$$. У него есть всего $$$n$$$ шариков, цвет $$$i$$$-го из них – $$$a_i$$$. Времени до турнира остается все меньше и меньше. Поэтому учитель позвал к себе на помощь ровно $$$k$$$ ассистентов. Он даст каждому из них отдельно по одному шарику и скажет ему перекрасить этот шарик в другой цвет. Он должен попросить всех ассистентов, потому что некоторые из них могут обидеться, увидев, что другой ассистент отдыхает. А также он обязательно должен отправить ассистента для перекраски шарика, ведь иначе ассистент останется без работы.

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

На этот вопрос придется уже ответить вам.

В нашем университете очень часто проводятся разные мероприятия для студентов. Даже в условиях карантина университет отлично справился со своей задачей и не переставал радовать своих студентов в онлайне. Ждем всех свеженьких на SDU Welcome Party 2021!

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

• Если партия заканчивалась вничью, оба игрока получали ровно $$$1$$$ очко.
• Иначе, победивший получал $$$3$$$ очка, а проигравший не получал ничего.

BThero знает результаты каждого игрока. $$$i$$$-й игрок имел ровно $$$a_i$$$ очков после завершения турнира. Однако BThero не знает сколько партий было сыграно в турнире суммарно. Помогите ему узнать минимальное и максимальное количество партий, которые могли быть сыграны в турнире.

Студенты Suleyman Demirel University ведут очень активный образ жизни. У нас в университете активно действуют более $$$20$$$ разных клубов. Абу, наш главный герой, на сей раз решил попробовать себя в MMDANCE Club. Пока что у него это неплохо получается.

Танцпол можно представить сверху как матрицу $$$A$$$ размера $$$n \times m$$$, где каждая клетка матрицы представляет собой отдельный сектор танцпола. В каждом секторе танцпола стоит ровно один танцор, и его высота равна $$$A_{i, j}$$$. В нашем случае можно считать что росты всех студентов — различные целые числа от $$$1$$$ до $$$n \times m$$$.

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

• Обозначим $$$S_{i, j}$$$ как отсортированное множество ростов всех танцоров, которые стоят по направлению левее, правее, выше и ниже танцора в секторе $$$(i, j)$$$. Это множество также содержит рост этого же танцора $$$A_{i, j}$$$. Более формально, $$$S_{i,j}$$$ содержит все числа находящиеся в $$$i$$$-й строке или $$$j$$$-м столбце матрицы $$$A$$$. У всех этих множеств одинаковая длина — $$$n+m-1$$$.
• Возьмём все эти множества $$$S_{i,j}$$$, запишем их всех в один список $$$T$$$ и отсортируем их лексикографически по возрастанию.
• Крутостью сектора $$$(i,j)$$$ будем считать порядковый индекс множества $$$S_{i,j}$$$ в списке $$$T$$$.

Пока Вы читали условие, Абу уже рассказал своим друзьям значения крутости всех секторов. А сможете вы?

Ербол агай ведет уроки программирования по Java для первокурсников. Семестр уже подходит к концу, а его студентам нужно защитить проект по Танчикам Денди (да-да, это действительно был их проект).

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

Ербол агай решил приготовиться и сделал $$$m$$$ самостоятельных расчетов. В каждом отдельном расчете он выбирает некоторый отрезок студентов $$$(l, r)$$$ и записывает количество нервных клеток $$$c$$$, которые умерли бы у него за день, если бы в этот день он принимал защиту проекта только от студентов с номерами в очереди на отрезке $$$[l, r]$$$.

Вот незадача! Сегодня утром Ербол агай случайно удалил список его студентов, стоящих в очереди. Повезло, что хотя бы результаты его расчетов остались в целостности и сохранности. Поскольку он уже не сможет восстановить свой список однозначно, он хотел бы определить хотя бы гендер каждого студента в очереди. Если возможны несколько очередей, его устраивает любой. Помогите агаю, восстановите очередь студентов в виде строки из $$$n$$$ символов x (юноша) и y (девушка).

Диас недавно начал изучать машинное обучение. Особенно сильно ему понравилась сфера распознавания различных паттернов в фотографиях. Недавно ему пришлось работать с распознаванием так называемых алмазов с некоторыми свойствами. Алмазы, по своей сути, имеют форму обычной квадратной рамки, повернутой на $$$45$$$ градусов.

Диас справился со своей задачей в машинном обучении. Теперь ему стало интересно, а смогут ли решить эту задачу наши любимые ACM-щики? Поскольку в машинном обучении люди работают с настоящими фотографиями у которых могут быть разные неровности и размытости, Диас адаптировал свою задачу специально для наших ребят: они могут считать, что фотография является бинарной матрицей размера $$$n \times n$$$. Строки и столбцы матрицы пронумерованы от $$$1$$$ до $$$n$$$.

Определим понятие алмазов в данной задаче более подробно. Каждый алмаз можно описать тремя положительными целыми числами — его центром $$$(p, q)$$$ и его радиусом $$$r$$$. Все клетки $$$(x, y)$$$, образующие сам алмаз, будут соответствовать свойству $$$|x - p| + |y - q| = r$$$. На картинке ниже приведены алмазы $$$(2, 2, 1)$$$, $$$(4, 3, 1)$$$ и $$$(3, 3, 2)$$$.

Диас попросил ACM-щиков посчитать общее количество алмазов на фотографии со следующими свойствами:

1. Алмаз находится полностью внутри матрицы. Более формально, все клетки $$$(x, y)$$$ принадлежащие алмазу соответствуют условию $$$1 \le x, y \le n$$$.
2. Все клетки алмаза содержат только единицы.

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

В SDU есть давняя традиция – собираться по выходным в университете и устраивать киномарафоны. Абу и Арс опять не могут решить какие фильмы выбрать для просмотра. Так как они устали от классического камень, ножницы, бумага, то они придумали новую интересную игру, которая разрешила бы их спор.

У игроков есть дерево из $$$n$$$ вершин и $$$n-1$$$ ребер. На одной из вершин дерева стоит фишка. А также есть список из $$$k$$$ запрещенных вершин. За свой ход Абу может удалить любое ребро из дерева. За свой ход Арс может передвинуть фишку в соседнюю вершину по любому не удаленному ребру или остаться на той же вершине. Первым ходит Абу. Игра заканчивается когда в дереве больше не осталось ребер. Арс выигрывает если в какой-то момент фишка оказалась на запрещенной вершине.

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

Вот и настал тот самый день когда Абу впервые переступил порог Самого Дружного Университета (СДУ) распахнув перед собой двери к бесценным знаниям. С первых же дней в стенах нового для себя заведения он начал всех удивлять своими знаниями и навыками в программировании. Все сокурсники завидовали ему, а учителя гордились что к ним в универ поступил такой сильный студент и видели в нём нового Илона Маска.

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

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

- Слушайте, студенты! Того, кто решит мою задачу первым, я возьму к себе в ассистенты и буду выплачивать ему большую сумму! – громко огласил профессор. Абу, с загоревшимися глазами, умчался в эту толпу, чтобы попытать своё счастье. В оригинальной формулировке задача звучала так:

У вас есть перестановка $$$p$$$ целых чисел от $$$1$$$ до $$$n$$$. А также у вас есть $$$m$$$ пар целых чисел $$$(a_i, b_i)$$$. За одну операцию вам разрешено выбрать произвольное целое число $$$i$$$ ($$$1 \le i \le m$$$) и сделать операцию swap(p[a[i]], p[b[i]]). Другими словами, вы меняете местами значения на позициях $$$a_i$$$ и $$$b_i$$$.

Есть одно важное ограничение — четность суммарного количества использований $$$i$$$-й пары во всех ваших операциях должна быть в точности равна $$$c_i$$$.

Вам нужно сделать $$$p$$$ лексикографически минимальным за не более $$$600000$$$ операций, при этом соблюдая все ограничения. Абу надеется на вашу помощь. На кону стоит его ретейк!

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

Корпус Suleyman Demirel University состоит из $$$n$$$ учебных кабинетов, расположенных в один ряд и пронумерованных от $$$1$$$ до $$$n$$$ слева направо. Новые перваши уже этой осенью поступят в наш чудесный универ, поэтому учитель программирования придумал классную задачку чтобы проверить их логику.

Ровно два кабинета из $$$n$$$ является кабинетами программирования. Скажем, что их номера — $$$a$$$ и $$$b$$$. Поскольку перваши в самом начале не будут знать номера этих кабинетов, учитель решил их загадать.

Все перваши подойдут к произвольному кабинету под номером $$$x$$$. Учитель, сидящий в этом кабинете, подскажет студентам сумму расстояний до кабинетов программирования. Более формально, он скажет им значение $$$|x - a| + |x - b|$$$. Затем перваши снова подойдут к произвольному кабинету $$$y$$$ и процесс будет повторяться до тех пор, пока перваши не будут уверены что нашли оба $$$a$$$ и $$$b$$$. Вполне возможно, что они в процессе уже посетят кабинет программирования, но хитрые учителя не станут это им раскрывать.

Алмас находится среди этих первашей. Он принял на себя роль мозга этой группы. Его цель — помочь своим одногруппникам найти $$$a$$$ и $$$b$$$ посетив как можно меньше кабинетов. Он уверен, что это возможно сделать за не более чем $$$50$$$ посещений. Помогите ему!

Взаимодействие начинается с чтения единственного целого числа $$$n$$$ — общего количества кабинетов в университете ($$$2 \le n \le 10^9$$$).

Далее программа будет отвечать на ваши запросы. Каждый запрос необходимо задавать в формате ? x ($$$1 \le x \le 10^9$$$). Перваши посетят кабинет под номером $$$x$$$. Затем нужно прочитать ответ учителя из стандартного ввода. Если учитель ответит $$$−1$$$ вместо корректного ответа, это означает, что перваши превысили $$$50$$$ посещений, или вы сделали некорректный запрос. Немедленно завершитесь после получения $$$−1$$$, чтобы получить вердикт Wrong answer. Иначе, вы можете получить произвольный вердикт, потому что ваше решение будет продолжать читать из закрытого потока.

Если вы угадали оба кабинета, выведите ответ в формате ! a b и завершите программу ($$$1 \le a \lt b \le n$$$).

После вывода запроса или ответа не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

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

Вам дан массив $$$a$$$ длины $$$n$$$ состоящий из положительных целых чисел. Обозначим $$$f(a)$$$ как массив $$$b$$$ длины $$$n-1$$$, где $$$b_i = gcd(a_1 + \dots + a_i, a_{i+1} + \dots + a_n)$$$. Будем применять операцию $$$a = f(a)$$$ до тех пор, пока размер массива $$$a$$$ не станет равным $$$1$$$. Выведите единственное оставшееся число в массиве.

Здесь $$$gcd(x, y)$$$ означает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.