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

Обозначим количество рублей на счёте клиента числом $$$n$$$. Для улучшения взаимодействия с клиентами банку необходимо узнать, сколько делителей больше или равных $$$10^{15}$$$ у числа $$$n$$$.

Помогите Алексею справиться с этой задачей.

На одной из площадок олимпиады по физкультуре «Мышечные технологии» есть две аудитории. Между ними расположены $$$n$$$ столов, на которых лежат пиццы, на $$$i$$$-м столе находятся $$$a_i$$$ пицц. При этом первая аудитория находится перед первым столом, а вторая — после последнего стола.

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

В разных аудиториях участникам были предложены разные задачи. Поэтому, если участник из первой аудитории видит, как участник из второй аудитории ест пиццу со стола на расстоянии не больше $$$k$$$, он немедленно начнёт обсуждать с ним задачи. Или же, более формально, пусть для участника из первой аудитории $$$x$$$ — номер ближайшего к нему стола с пиццей, а $$$y$$$ — номер стола с пиццей для участника из второй аудитории, тогда, если $$$y - x \leq k$$$, то они немедленно начнут обсуждать задачи.

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

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

Учёные-немалисты рассчитали ограничения, которые обеспечат безопасность телепортационной сети. Для каждого телепорта было выписано слово $$$s_i$$$ соответственно. За $$$|s_i|$$$ они обозначили длину строки $$$i$$$. Также они выбрали целое число $$$k$$$. Учёные разрешили горожанам телепортироваться из телепорта $$$i$$$ в телепорт $$$j$$$ при условии, что пассажир предъявит такое число $$$m$$$, что:

• суффикс $$$s_i$$$ длины $$$m$$$ равен префиксу $$$s_j$$$ длины $$$m$$$;
• суффикс $$$s_i$$$ длины $$$m + 1$$$ не равен префиксу $$$s_j$$$ длины $$$m + 1$$$ (в частности, если $$$m + 1 \gt \min(|s_i|, |s_j|)$$$);
• $$$k \le m \leq \min(|s_i|, |s_j|)$$$ (по Федеральному Закону «О немалости операций»).

При этом стоимость такой телепортации составляет $$$m$$$ немалей (местная валюта).

Например, для $$$s_i =$$$ «abcde» и $$$s_j =$$$ «cdef» подходит только $$$m = 3$$$, и стоить такая телепортация будет $$$3$$$ немаля.

Мэр города, Немалуй, собирает сведения об эффективности телепортов. Для каждого телепорта $$$i$$$ ($$$2 \le i \le n$$$) вам нужно найти минимальное число немалей, необходимое для того, чтобы добраться от $$$1$$$-го телепорта до телепорта $$$i$$$, совершив какое-то количество телепортаций.

Вам дана перестановка $$$p$$$ всех чисел от $$$1$$$ до $$$n$$$, а также целое число $$$k$$$. С перестановкой разрешается выполнять следующую операцию неограниченное число раз:

1. Выбрать любой подотрезок длины $$$k$$$.
2. Найти на этом подотрезке минимальный и максимальный элементы.
3. Поменять их местами.

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

Наконец-то выпустили долгожданный ремастер вашей любимой Flash игры Warfare 1917! Вы так долго его ждали, что отложили все свои дела и бросились играть. Работавшие над игрой креативные менеджеры решили, что предпочтения игроков за последние 17 лет сильно поменялись, поэтому многие игровые механики были упрощены. В то же время менеджеры постарались сохранить бюджет дух оригинала, поэтому приняли решение переиспользовать старые графические ресурсы.

В игре сражаются два игрока, каждый имеет на руках карты со значениями от $$$1$$$ до $$$6$$$, соответствующие юнитам из оригинальной игры, и по ноль очков. Карта с большим значением бьёт карту с меньшим. Игра проходит в шесть раундов, каждый раунд игроки одновременно выбирают и разыгрывают по карте. Если значения карт совпадают, ничего не происходит, в противном случае игрок с большим значением получает одно очко. Разыгранные карты переиспользовать нельзя. Если один из игроков набрал больше очков, чем другой, он объявляется победителем игры.

Вы будете сражаться с ботами, которые играют по следующим стратегиям:

1. Каждая карта — минимальная в руке бота (в данный момент);
2. Каждая карта — максимальная в руке бота (в данный момент);
3. Первые три карты — $$$1, 2, 3$$$ (в случайном порядке), следующие три карты — $$$4, 5, 6$$$ (в случайном порядке);
4. Первые три карты — $$$4, 5, 6$$$ (в случайном порядке), следующие три карты — $$$1, 2, 3$$$ (в случайном порядке);
5. Каждая карта — случайная из двух минимальных в руке бота (в данный момент);
6. Каждая карта — случайная из двух максимальных в руке бота (в данный момент);
7. Каждая карта — случайная из трёх минимальных в руке бота (в данный момент);
8. Каждая карта — случайная из трёх максимальных в руке бота (в данный момент).

Каждый тест соответствует одному боту, при этом порядок тестов соответствует порядку ботов в описании. В каждом тесте вы сыграете с ботом $$$500$$$ независимых игр. Ваша задача — выиграть у каждого бота хотя бы $$$251$$$ игру. Ничья не считается за победу.

Обратите внимание, что боты не меняют свою стратегию, но при этом случайность равномерно распределена и работает независимо для каждой игры. Например, третий бот может сыграть последовательность карт $$$1, 3, 2, 5, 6, 4$$$ в первой игре и $$$2, 3, 1, 4, 5, 6$$$ во второй.

Вы сыграете с каждым ботом $$$500$$$ раз.

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

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

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

Не забывайте сбрасывать буфер после каждого вывода. Для этого можете использовать std::endl в C++ или стандартную функцию print в Python. Не используйте ios_base::sync_with_stdio(false) в C++.

Интерактор не является адаптивным, то есть ходы ботов зафиксированы заранее и не зависят от ваших действий.

У Артема есть массив $$$a$$$ длины $$$n$$$. Ему не нравится, когда в массиве есть различные значения, поэтому он просит вас исправить это.

Вам разрешено выполнять операции, которые преобразуют массив. За одну операцию вы можете выбрать три целых числа $$$l$$$, $$$r$$$, $$$x$$$, если $$$\lceil\frac{n}{2}\rceil \le r - l + 1$$$. Тогда для всех $$$i$$$, что $$$l \le i \le r$$$, применяется изменение $$$a_i = a_i \oplus x$$$, где $$$\oplus$$$ обозначает побитовое «исключающее или».

Скажите, можно ли сделать все элементы массива равными, выполнив не более $$$n - 1$$$ операций.

Назовём массив $$$b_1,b_2,\ldots,b_{2k-1}$$$, $$$k$$$-древесным, для целого $$$k \geq 2$$$, если его элементы можно переставить таким образом, чтобы одновременно были выполнены следующие условия:

• $$$b_1 = k$$$
• Если рассмотреть граф, в котором есть вершины, соответствующие всем различным значениям среди $$$b_2, b_3, \ldots, b_{2k-1}$$$, и провести в нём $$$k-1$$$ рёбер между вершинами с значениями $$$b_2$$$ и $$$b_3$$$, $$$b_4$$$ и $$$b_5$$$, ..., $$$b_{2k-2}$$$ и $$$b_{2k-1}$$$, то получившийся граф должен быть деревом$$$^{\text{∗}}$$$

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

Например, массив $$$[4, 100, 4, 3, 3]$$$ является $$$3$$$-древесным, так как его элементы можно переставить в $$$[3, 3, 4, 4, 100]$$$, и граф с рёбрами $$$3 \leftrightarrow 4$$$, $$$4 \leftrightarrow 100$$$ является деревом из $$$3$$$ вершин.

Вам дан массив $$$a_1, a_2, \ldots, a_n$$$ и $$$q$$$ запросов. В каждом запросе даны два числа $$$1 \leq l \leq r \leq n$$$, и нужно найти количество целых $$$k \geq 2$$$ таких, что у массива $$$a_l, \ldots, a_r$$$ есть хотя бы одна $$$k$$$-древесная подпоследовательность.

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

Алиса и Боб играют в следующую игру. Изначально у Алисы есть $$$n$$$ карточек с числами $$$a_1, a_2, \ldots, a_n$$$ из неотрицательных чисел, меньших $$$m$$$. Также задана фиксированная бинарная строка $$$s_0s_1 \ldots s_{m-1}$$$.

Каждый ход Алиса может совершить одно из следующих действий:

• Выбрать две свои карточки. Пусть числа, записанные на них — $$$x$$$ и $$$y$$$. Тогда Алиса убирает обе карточки с числами $$$x$$$, $$$y$$$ и заменяет их одной карточкой с числом $$$(x + y) \bmod m$$$.
• Выбрать одну свою карточку. Пусть число, записанное на ней — $$$x$$$. Тогда Алиса может попросить Боба заменить эту карточку на некоторое число от $$$0$$$ до $$$m-1$$$ включительно не равное $$$x$$$. Обратите внимание, что число на новой карточке выбирает Боб.
• Закончить игру.

Если через $$$n + m+7$$$ ходов Алиса не закончила игру, или у неё на руках всё ещё больше одной карты, победителем считается Боб. Иначе у Алисы на руках одна карточка. Пусть на этой карточке число $$$x$$$. Тогда, если $$$s_x = 1$$$, в игре побеждает Алиса, а иначе побеждает Боб.

Ваша задача — выбрать, за какого игрока играть, и выиграть игру с программой жюри.

Взаимодействие начинается со считывания входных данных. Первая строка каждого набора входных данных содержит два целых числа $$$n, m$$$ ($$$2 \le n \le 100$$$, $$$2 \le m \le 100$$$) — длину массива $$$a$$$ и модуль.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \lt m$$$) — элементы массива $$$a$$$.

Третья строка каждого набора входных данных содержит бинарную строку длины $$$m$$$ — $$$s_0s_1 \ldots s_{m-1}$$$.

После считывания данных вы должны вывести одну строку: Alice или Bob — имя игрока, за которого вы будете играть.

Если вы выбрали играть за Алису, далее выводите совершаемые операции в следующем формате:

• unite $$$x$$$ $$$y$$$ — для объединения карточек с числами $$$x$$$ и $$$y$$$ в одну карточку с числом $$$(x + y) \bmod m$$$.
• replace $$$x$$$ — для замены карточки с значением $$$x$$$. После вывода в одной строке считайте число $$$y$$$ ($$$0 \le y \lt m$$$, $$$y \neq x$$$) — значение новой карточки, выбранное Бобом.
• done — закончить игру.

Если вы выбрали играть за Боба, далее считывайте операции Алисы в таком же формате. На каждую операцию replace $$$x$$$ — вам нужно вывести число $$$y$$$ ($$$0 \le y \lt m$$$, $$$y \neq x$$$) в отдельной строке. Также гарантируется, что программа жюри, играющая за Алису, закончит игру за не более чем $$$n + m + 7$$$ ходов, с одной картой на руках.

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

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло». На любом шаге взаимодействия, если вы считали -1 вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.

У вас есть два корневых дерева $$$t_1$$$ и $$$t_2$$$, состоящие из $$$n_1$$$ и $$$n_2$$$ вершин соответственно.

Корневое дерево — это дерево с выделенной вершиной, которую называют корнем.

В каждой вершине деревьев $$$t_1$$$ и $$$t_2$$$ записано целое число — вес данной вершины.

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

1. Спуститься по дереву от корня до каждого листа, считая XOR весов всех вершин на пути.
2. Сложить получившиеся значения для всех листов.

XOR — это операция побитового исключающего ИЛИ, обозначаемая символом $$$\oplus$$$. При вычислении выражения $$$a \oplus b$$$ каждый бит результата будет равен $$$0$$$, если соответствующие биты чисел $$$a$$$ и $$$b$$$ равны, и равен $$$1$$$ иначе.

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

1. XOR весов на пути до первого листа равен $$$3 \oplus 6 = 5$$$.
2. XOR весов на пути до второго листа равен $$$3 \oplus 4 = 7$$$.
3. XOR весов на пути до третьего листа равен $$$3 \oplus 2 \oplus 1 = 0$$$.
4. XOR весов на пути до четвёртого листа равен $$$3 \oplus 2 \oplus 5 = 4$$$.
5. Вес всего дерева равен $$$5 + 7 + 0 + 4 = 16$$$.

Корневое дерево из 6 вершин.

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

Другими словами, необходимо выполнить одну из следующих операций:

• Выбрать вершину $$$i$$$ ($$$1 \le i \le n_1$$$) в дереве $$$t_1$$$ и провести от неё ребро к вершине, являющейся корнем дерева $$$t_2$$$.
• Выбрать вершину $$$j$$$ ($$$1 \le j \le n_2$$$) в дереве $$$t_2$$$ и провести от неё ребро к вершине, являющейся корнем дерева $$$t_1$$$.

В результате получится новое дерево $$$t$$$, состоящее из $$$n_1 + n_2$$$ вершин. Необходимо найти дерево $$$t$$$ такое, вес которого будет максимальным среди всех возможных деревьев, которые можно получить выполнением одной из операций выше.

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

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

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

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

Ксюша — именитый эксперт в области компьютерной безопасности. Известная корпорация, разрабатывающая программное обеспечение RISC-V процессоров, наняла Ксюшу для расследования недавнего инцидента. Неопознанный горилл пробрался в продовый контур корпорации и похитил секретную разработку — массив из $$$n$$$ положительных целых чисел $$$a_1, a_2, \ldots, a_n$$$. Известно, что этот массив был упорядочен по неубыванию ($$$1 \le a_1 \le a_2 \le \ldots \le a_n$$$).

Неопознанный горилл — опытный хакер, поэтому он придумал, как обойти периметр фильтрации внутреннего трафика и извлечь массив $$$a$$$ во внешнюю сеть. Горилл дописал в конец массива $$$a$$$ элементы $$$a_1, a_1 + a_2, \ldots, a_1 + a_2 + \ldots + a_n$$$, другими словами, элементы массива префиксных сумм $$$a$$$. Затем горилл перемешал получившийся массив длины $$$2n$$$ случайным образом и назвал его $$$b$$$.

Ксюша смогла восстановить массив $$$b$$$ из логов, но чтобы оценить ущерб, нанесённый корпорации, необходимо восстановить похищенный массив $$$a$$$. Это слишком простая задача для Ксюши, поэтому её предстоит выполнить вам.