Задано корневое неориентированное дерево, состоящее из \(n\) вершин. Вершина \(1\) является корнем.

Определим массив глубин вершины \(x\), как бесконечную последовательность \([d_{x, 0}, d_{x, 1}, d_{x, 2}, \dots]\), где \(d_{x, i}\) — это количество вершин \(y\) таких, что выполняются оба следующих условия:

• \(x\) является предком \(y\);
• простой путь из \(x\) в \(y\) проходит ровно по \(i\) ребрам.

Доминирующий индекс массива глубин вершины \(x\) (или же просто доминирующий индекс вершины \(x\)) — это такой индекс \(j\), что:

• для каждого \(k < j\), \(d_{x, k} < d_{x, j}\);
• для каждого \(k > j\), \(d_{x, k} \le d_{x, j}\).

Для каждой вершины дерева вычислите ее доминирующий индекс.

Вам дан массив из \(n\) целых положительных чисел \(a_1, a_2, \dots, a_n\). К массиву можно применять следующие операции: выбрать несколько различных индексов этого массива \(i_1, i_2, \dots, i_k\) (\(1 \le i_j \le n\)) и переместить число, стоящее на позиции \(i_1\) на позицию \(i_2\), число стоящее на позиции \(i_2\) на позицию \(i_3\), ..., число на позиции \(i_k\) на позицию \(i_1\). То есть сдвинуть элементы по циклу \(i_1 \to i_2 \to \ldots i_k \to i_1\).

К примеру, если у вас есть \(n=4\), массив \(a_1=10, a_2=20, a_3=30, a_4=40\), и вы выбрали три индекса \(i_1=2\), \(i_2=1\), \(i_3=4\), то получившийся массив будет \(a_1=20, a_2=40, a_3=30, a_4=10\).

Вам дано целое неотрицательное число \(s\). Отсортируйте массив с помощью минимально возможного количества таких операций, при условии, что сумма размеров циклов для всех операций не превосходит \(s\), или скажите, что это невозможно.

Поликарп учится в Берляндском государственном университете. Совсем скоро ему предстоит сдать сессию. Он должен сдать \(n\) экзаменов.

Для каждого экзамена \(i\) известны два дня: \(a_i\) — день основной сдачи экзамена, \(b_i\) — день пересдачи (\(a_i < b_i\)). В один день Поликарп может сдавать не более одного экзамена. Для каждого экзамена Поликарп самостоятельно выбирает, в какой из двух дней его сдать. Необходимо сдать все \(n\) экзаменов.

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

К компьютерной сети Метрополии подключены \(n\) серверов, каждому из которых назначен некоторый ключ шифрования, выбранный в диапазоне от \(0\) до \(2^k - 1\) включительно. Обозначим через \(c_i\) ключ шифрования, назначенный \(i\)-му серверу. Также некоторые \(m\) пар серверов напрямую соединены каналом передачи данных. Из-за особенностей используемых алгоритмов шифрования канал передачи данных безопасен, только если два соединённых этим каналом сервера используют различные ключи шифрования. Изначально ключи шифрования выбраны таким образом, что все каналы передачи данных безопасны.

Вам стало известно, что по интернету активно распространяется новый вирус, который при заражении им какого-либо сервера Метрополии изменяет его ключ шифрования. А именно, в теле вируса хранится некоторое неизвестное вам число \(x\), выбранное в том же диапазоне, и если вирусом заразится сервер \(i\), то его ключ шифрования изменится с \(c_i\) на \(c_i \oplus x\), где \(\oplus\) обозначает операцию побитового исключающего ИЛИ.

К сожалению, вы не знаете ни число \(x\), ни какие именно серверы Метрополии будут заражены опасным вирусом, поэтому решили посчитать количество вариантов, при которых безопасность каналов нарушена не будет. Формально, вам требуется найти количество пар \((A, x)\), где \(A\) — некоторое подмножество серверов (возможно пустое), а \(x\) — возможное значение внутреннего параметра вируса в диапазоне от \(0\) до \(2^k - 1\) включительно, таких что если вирус с параметром \(x\) заразит компьютеры из подмножества \(A\), а остальные компьютеры заражены не будут, то все каналы передачи данных останутся безопасными. Поскольку эта величина может быть достаточно большой, найдите остаток от её деления на \(10^9 + 7\).

Есть массив \(a\) из \(2^{30}\) целых чисел, пронумерованных от \(0\) до \(2^{30}-1\). Изначально вы знаете, что \(0 \leq a_i < 2^{30}\) (\(0 \leq i < 2^{30}\)), но вы не знаете эти числа. Ваша задача заключается в том, чтобы обработать все запросы двух видов:

• 1 l r x: Вам сообщают, что исключающее ИЛИ (он же XOR) подотрезка \([l, r]\) (включительно) равно \(x\). То есть \(a_l \oplus a_{l+1} \oplus \ldots \oplus a_{r-1} \oplus a_r = x\), где \(\oplus\) — побитовое исключающее ИЛИ. В некоторых случаях полученный запрос противоречит предыдущим запросам. В этом случае нужно проигнорировать противоречивый запрос (новый запрос).
• 2 l r: Нужно вывести исключающее ИЛИ подмассива \([l, r]\) (включительно). Если же, используя все предыдущие запросы, ответить на этот запрос невозможно, нужно вывести \(-1\).

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

Допустим, у вас есть последовательность \(S\) из \(k\) пар целых чисел \((a_1, b_1), (a_2, b_2), \dots, (a_k, b_k)\).

Вы можете совершать с ней следующие операции:

1. Выбрать некоторую позицию \(i\) и увеличить \(a_i\) на \(1\). Эту операцию можно делать только в том случае, если существует хотя бы одна позиция \(j\), такая, что \(i \ne j\) и \(a_i = a_j\). Стоимость такой операции равна \(b_i\);
2. Выбрать некоторую позицию \(i\) и уменьшить \(a_i\) на \(1\). Эту операцию можно делать только в том случае, если существует хотя бы одна позиция \(j\), такая, что \(a_i = a_j + 1\). Стоимость такой операции равна \(-b_i\).

Каждая операция может быть использована любое количество раз (возможно, ноль).

Обозначим за \(f(S)\) такое минимально возможное \(x\), что существует последовательность операций с суммарной стоимостью \(x\), после которой все \(a_i\) в \(S\) станут попарно различными.

А теперь, собственно, сама задача.

Вам дана последовательность \(P\), состоящая из \(n\) пар целых чисел \((a_1, b_1), (a_2, b_2), \dots, (a_n, b_n)\). Все значения \(b_i\) попарно различны. Пусть \(P_i\) — это последовательность, состоящая из первых \(i\) пар из \(P\). Ваша задача — подсчитать \(f(P_1), f(P_2), \dots, f(P_n)\).

Chouti устал от утомительного домашнего задания и решил открыть старую задачу, которую он придумал несколько лет назад.

Дан связный неориентированный граф, состоящий из \(n\) вершин и \(m\) взвешенных ребер. Также есть \(k\) выделенных вершин: \(x_1, x_2, \ldots, x_k\).

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

Для каждой выделенной вершины найдите другую выделенную вершину, которая является максимально далёкой от неё (в терминах абзаца выше, то есть соответствующее расстояние максимально возможное), и выведите расстояние между ними.

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

Вам дан неориентированный граф, состоящий из \(n\) вершин. На каждой вершине записано число; число, записанное на вершине \(i\), равно \(a_i\). Изначально в графе нет ни одного ребра.

Вы можете добавлять ребра в граф за определенную стоимость. За добавление ребра между вершинами \(x\) и \(y\) надо заплатить \(a_x + a_y\) монет. Также существует \(m\) специальных предложений, каждое из которых характеризуется тремя числами \(x\), \(y\) и \(w\), и означает, что можно добавить ребро между вершинами \(x\) и \(y\) за \(w\) монет. Эти специальные предложения не обязательно использовать: если существует такая пара вершин \(x\) и \(y\), такая, что для нее существует специальное предложение, можно все равно добавить ребро между ними за \(a_x + a_y\) монет.

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

Задан неориентированный взвешенный связный граф, состоящий из \(n\) вершин и \(m\) ребер без петель и кратных ребер.

\(i\)-е ребро — \(e_i = (u_i, v_i, w_i)\); расстояние между вершинами \(u_i\) и \(v_i\) по ребру \(e_i\) равно \(w_i\) (\(1 \le w_i\)). Граф является связным, то есть для каждой пары вершин существует хотя бы один путь между ними, состоящий только из ребер заданного графа.

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

Вы можете модифицировать заданный граф. Единственная операция, которую вы можете проводить, заключается в следующем: увеличить вес какого-либо ребра на \(1\). Вы можете увеличивать вес каждого ребра любое (возможно, нулевое) количество раз.

Предположим, что изначальный вес MST был равен \(k\). Ваша задача — увеличить веса некоторых ребер за минимально возможное количество операций таким образом, чтобы вес MST в получившемся графе остался равен \(k\), но MST стало уникальным (это означает, что есть только один способ выбрать MST в получившемся графе).

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

Алиса живет на плоской земле, которая может быть представлена как квадратная решетка \(n \times n\) со строками и столбцами, пронумерованными от \(1\) до \(n\). Обозначим клетку на пересечении строки \(r\) и столбца \(c\) упорядоченной парой \((r, c)\). Каждая клетка решетки является либо землей, либо водой.

Пример планеты с \(n = 5\). Она также является первым примером.

Алиса живет на клетке, которая является землей, \((r_1, c_1)\). Она хочет добраться до другой клетки, которая является землей, \((r_2, c_2)\). В любой момент она может переместиться в одну из соседних с ней ячеек — в одном из четырех направлений (т.е. вверх, вниз, влево или вправо).

К сожалению, Алиса не умеет плавать, и можно перемещаться только пешком (т.е. только по земле). В итоге путешествие Алисы может быть невозможно.

Чтобы помочь Алисе, вы хотите создать не более одного туннеля между какими-то двумя земляными клетками. Туннель позволяет Алисе перемещаться между двумя его концами. Создание туннеля требует некоторых затрат: стоимость туннеля между клетками \((r_s, c_s)\) и \((r_t, c_t)\) равна \((r_s-r_t)^2 + (c_s-c_t)^2\).

Таким образом, ваша задача — найти минимальную стоимость постройки не более одного туннеля так, чтобы Алиса смогла добраться от клетки \((r_1, c_1)\) до клетки \((r_2, c_2)\). Если постройка туннеля не обязательна, стоимость полагается равной \(0\).

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

Наблюдая за котятами, Ася заметила, что они очень дружелюбны и некоторые пары живущих в соседних ячейках котят очень хотят играть друг с другом. Чтобы не лишать их этого удовольствия, Ася стала вынимать перегородки между соседними ячейками. В частности, в \(i\)-й день, Ася:

• Обратила внимание, что котята \(x_i\) и \(y_i\), живущие в соседних ячейках, хотят играть вместе.
• Удаляла перегородку между этими ячейками, превращая их в одну, в которой оказывались все котята из двух прежних ячеек.

Поскольку Ася ни разу возвращала перегородки, через \(n - 1\) день вольер стал единой ячейкой, в которой оказались все котята.

Для каждого дня, Ася помнит номера котят \(x_i\) и \(y_i\), которые хотели играть вместе, однако она не помнит как котята были поселены в ячейки изначально. Помогите ей найти какое-нибудь возможное начальное расселение котят по \(n\) ячейкам.

Вам дано дерево (связный неориентированный граф без циклов), состоящее из \(n\) вершин. Каждое из \(n - 1\) рёбер дерева покрашено в чёрный или красный цвет.

Вам также дано целое число \(k\). Рассмотрим последовательности из \(k\) вершин. Скажем, что последовательность \([a_1, a_2, \ldots, a_k]\) является хорошей, если она удовлетворяет следующему:

• Мы пройдём некоторый путь в дереве (возможно посещающий несколько раз одну и ту же вершину или ребро), начинающийся в \(a_1\) и заканчивающийся в \(a_k\).
• Начнём в \(a_1\), затем перейдём в \(a_2\) по кратчайшему пути между \(a_1\) и \(a_2\), затем перейдём в \(a_3\) аналогичным образом, и так далее, пока наконец не пройдём кратчайший путь из \(a_{k-1}\) в \(a_k\).
• Если в результате такого процесса мы пройдём хотя бы по одному чёрному ребру, то последовательность является хорошей.

Рассмотрим дерево, изображенное на рисунке. Если \(k=3\), то следующие последовательности являются хорошими: \([1, 4, 7]\), \([5, 5, 3]\) и \([2, 3, 7]\). Следующие последовательности не являются хорошими: \([1, 4, 6]\), \([5, 5, 5]\), \([3, 7, 3]\).

Всего есть \(n^k\) последовательностей вершин, посчитайте сколько из них являются хорошими. Так как это число может быть очень большим, выведите его по модулю \(10^9+7\).

Задано дерево (неориентированный связный ацикличный граф), состоящее из \(n\) вершин и \(n - 1\) ребра. На каждом ребре записано число, каждое из чисел — это либо \(0\) (назовем такие ребра \(0\)-ребрами), либо \(1\) (назовем их \(1\)-ребрами).

Назовем упорядоченную пару вершин \((x, y)\) (\(x \ne y\)) корректной, если при проходе по простому пути от \(x\) до \(y\) мы никогда не пройдем по \(0\)-ребру после прохода по \(1\)-ребру. Ваша задача — посчитать количество корректных пар в дереве.

В одной волшебной стране ровно \(n\) городов, пронумерованных \(1, 2, \dots, n\). Некоторые пары городов соединены волшебными цветными дорогами. Волшебство непостоянно, поэтому иногда между городами возникают новые дороги.

Работа ведьмы Вики — доставлять посылки из одних городов в другие. Вики — новичок, поэтому она может выполнить доставку, только если существует двойной радужный путь из начального города в конечный. Двойным радужным путем называется последовательность городов \(c_1, c_2, \dots, c_k\), удовлетворяющая следующим свойствам:

• Для каждого \(i\), где \(1 \le i \le k - 1\), города \(c_i\) и \(c_{i + 1}\) соединены дорогой.
• Для каждого \(i\), где \(1 \le i \le \frac{k - 1}{2}\), дороги, соединяющие \(c_{2i}\) с городами \(c_{2i - 1}\) и \(c_{2i + 1}\), должны иметь один и тот же цвет.

Например, если \(k = 5\), то дорога между городами \(c_1\) и \(c_2\) должна быть того же цвета, что и дорога между \(c_2\) и \(c_3\), а дорога между \(c_3\) и \(c_4\) должна иметь тот же цвет, что и дорога между \(c_4\) и \(c_5\).

У Вики есть список событий в хронологическом порядке. Каждое событие — это либо доставка, которую она должна выполнить, либо появление новой дороги. Помогите ей определить, какие доставки она сможет выполнить.

Задан неориентированный невзвешенный связный граф, состоящий из \(n\) вершин и \(m\) ребер. Гарантируется, что в данном графе нет петель и кратных ребер.

Ваша задача — выбрать не более \(\lfloor\frac{n}{2}\rfloor\) вершин в данном графе так, чтобы каждая невыбранная вершина была смежна (другими словами, связана ребром) с хотя бы одной выбранной вершиной.

Гарантируется, что ответ существует. Если существует несколько решений, выведите любое из них.

Требуется ответить на несколько независимых запросов.

Легендарный фермер Джон готовит большую вечеринку. В гости были приглашены животные со всего мира. Сейчас гости проголодались, так что Джон попросил свою корову Бесси достать чего-нибудь перекусить.

Есть \(n\) разных видов закусок, пронумерованных числами \(1, 2, \ldots, n\). У Бесси есть \(n\) закусок, по одной закуске каждого вида. У каждого гостя есть ровно два любимых вида закусок. Процесс перекуса будет происходить следующим образом:

• Сначала Бесси упорядочит всех гостей в каком-то порядке.
• Затем, в этом порядке гости будут по одному подходить к закускам.
• Каждый гость будет в свой ход съедать все оставшиеся закуски любимых типов. В случае, если не осталось ни одной закуски любимых типов, то гость уйдёт очень грустным.

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

Авторы загадали строку \(s\), состоящую из \(n\) строчных букв латинского алфавита.

Вам задано две перестановки ее индексов (не обязательно одинаковых) \(p\) и \(q\) (обе длины \(n\)). Напомним, что перестановкой называется массив длины \(n\), содержащий каждое целое число от \(1\) до \(n\) ровно один раз.

Для всех \(i\) от \(1\) до \(n-1\) выполняются следующие свойства: \(s[p_i] \le s[p_{i + 1}]\) и \(s[q_i] \le s[q_{i + 1}]\). Это значит, что если вы выпишете все символы \(s\) в порядке индексов в перестановке, результирующая строка получится отсортированной в неубывающем порядке.

Ваша задача — восстановить любую строку \(s\) длины \(n\), состоящую хотя бы из \(k\) различных строчных букв латинского алфавита, которая подходит к заданным перестановкам.

Если существует несколько возможных ответов, вы можете вывести любой.

Дан неориентированный граф из \(n\) вершин и без ребер. Вершины пронумерованы от \(1\) до \(n\).

Необходимо ответить на запросы к нему. Пусть \(last\) будет ответом на предыдущий запрос второго типа (или \(0\), если таких запросов еще не было). Тогда запросы следующие:

• \(1~x~y\) (\(1 \le x, y \le n\), \(x \ne y\)) — добавить неориентированное ребро между вершинами \((x + last - 1)~mod~n + 1\) и \((y + last - 1)~mod~n + 1\), если такого в графе нет, а иначе удалить его;
• \(2~x~y\) (\(1 \le x, y \le n\), \(x \ne y\)) — проверить, что существует путь между вершинами \((x + last - 1)~mod~n + 1\) и \((y + last - 1)~mod~n + 1\), который проходит только через существующие ребра, и выставить \(last\) значение \(1\), если есть, и \(0\) иначе.

Удачи!

Алиса играет в игру со своей хорошей подругой, Марисой.

В линию располагается \(n\) коробок, пронумерованных слева направо целыми числами от \(1\) до \(n\). Мариса спрячет куклу в одной из коробок. Затем у Алисы будет \(m\) шансов угадать где находится кукла. Если Алиса хотя бы раз верно угадает номер коробки, в которой сейчас находится кукла, то она победит, иначе победит ее подруга.

Для того, чтобы победить, Мариса будет использовать некоторые нечестные трюки. После каждого раза, когда Алиса пыталась угадать коробку, она может переместить куклу в соседнюю коробку или оставить на месте. Коробки с номерами \(i\) и \(i + 1\) являются соседними, для всех \(1 \leq i \leq n - 1\). Перед тем как игра начнется, она также может сделать этот трюк один раз.

Таким образом, игра происходит следующим образом: игра начинается, Мариса делает трюк, Алиса делает первое предположение, Мариса делает трюк, Алиса делает второе предположение, Мариса делает трюк, \(\ldots\), Алиса делает \(m\)-е предположение, Мариса делает трюк, игра заканчивается.

Алиса придумала некоторую последовательность \(a_1, a_2, \ldots, a_m\). В \(i\)-м вопросе, она спросит, находится ли кукла в коробке с номером \(a_i\). Она хочет узнать сколько существует различных сценариев \((x, y)\) (для всех \(1 \leq x, y \leq n\)), таких что Мариса сможет выиграть в игре, если она положит куклу в коробку с номером \(x\) в начале игры и после того, как игра закончится, кукла будет в коробке с номером \(y\). Помогите ей и посчитайте это число.

Шичикуджи — новое местное божество Южного Храма Черной Улитки. Ее первое задание заключается в следующем:

В префектуре X построено \(n\) новых городов. Города пронумерованы от \(1\) до \(n\). Город \(i\) находится в \(x_i\) км на север от храма и в \(y_i\) ем на восток от храма. Возможно, что \((x_i, y_i) = (x_j, y_j)\) даже если \(i \ne j\).

Шичикуджи планирует обеспечить электричеством каждый город либо с помощью установки там электростанции, либо с помощью соединения его с другим городом, в котором уже есть электричество. То есть в городе есть электричество, если в нём есть электростанция или он соединён напрямую или по цепочке кабелей с городом, в котором есть электростанция.

• Возведение электростанции в городе \(i\) стоит \(c_i\) иен;
• Соединение города \(i\) и города \(j\) стоит \(k_i + k_j\) иен за каждый км кабеля, использованного для соединения. Однако кабель можно прокладывать вдоль сторон света (на север, юг, восток, запад). Кабели могут пересекать друг друга. У каждого кабеля оба конца должны быть в некоторых городах. Если город \(i\) и город \(j\) соединены кабелем, то кабель всегда будет прокладываться по кратчайшему пути из города \(i\) в город \(j\). Тогда длина кабеля, соединяющего город \(i\) и город \(j\), равна \(|x_i - x_j| + |y_i - y_j|\) км.

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

Таким образом, от вас требуется предоставить Шичикуджи следующую информацию: минимальное количество иен, необходимое, чтобы обеспечить электричеством все города, города, в которых будут построены электростанции, и проведенные соединения.

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

Единственное отличие между простой и сложной версиями — ограничения.

Есть \(n\) детей, каждый из которых читает уникальную книгу. В конце каждого дня \(i\)-й ребёнок отдаёт свою книгу \(p_i\)-му ребёнку (в случае, когда \(i = p_i\) ребенок отдает свою книгу самому себе). Гарантируется, что все значения \(p_i\) — различные целые числа от \(1\) до \(n\) (то есть \(p\) — перестановка). Последовательность \(p\) не меняется изо дня в день, она фиксированная.

Например, если \(n=6\) и \(p=[4, 6, 1, 3, 5, 2]\), то в конце первого дня книга \(1\)-го ребёнка будет у \(4\)-го ребёнка, книга \(2\)-го ребёнка будет у \(6\)-го ребёнка и так далее. В конце второго дня книга \(1\)-го ребёнка будет у \(3\)-го ребёнка, книга \(2\)-го ребёнка будет у \(2\)-го ребёнка и так далее.

Перед вами стоит задача — для каждого \(i\) от \(1\) до \(n\) определить число дней, через которое книга \(i\)-го ребёнка вернётся обратно к нему в первый раз.

Предположим что \(p = [5, 1, 2, 4, 3]\). Книга \(1\)-го ребёнка будет передана следующим детям:

• после \(1\)-го дня она будет у \(5\)-го ребёнка,
• после \(2\)-го дня она будет у \(3\)-го ребёнка,
• после \(3\)-го дня она будет у \(2\)-го ребёнка,
• после \(4\)-го дня она будет у \(1\)-го ребёнка.

Таким образом, после четвертого дня книга первого ребёнка вернётся к своему владельцу. Книга четвёртого ребёнка вернётся к нему в первый раз сразу после первого дня.

Вы должны ответить на \(q\) независимых запросов.

Вам дан простой, неориентированный, связный взвешенный граф с \(n\) вершинами и \(m\) ребрами.

Вершины пронумерованы от \(1\) до \(n\). Есть ровно \(k\) центров (точек перезарядки), находящихся в вершинах \(1, 2, \ldots, k\).

Рассмотрим робота, двигающегося по этому графу, с батареей емкости \(c\), пока не фиксированной конструктором. В любой момент времени батарея может содержать целое количество \(x\) энергии от \(0\) до \(c\) включительно.

Переход по ребру веса \(w_i\) возможен, только если \(x \ge w_i\), и это стоит \(w_i\) энергии (\(x := x - w_i\)).

Когда робот достигает центра, его батарея полностью перезаряжается (\(x := c\)).

Вам дано \(q\) независимых миссий, в \(i\)-й миссии роботу требуется добраться от центра \(a_i\) до центра \(b_i\).

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

Один малоизвестный хакер захотел заполучить пароль администратора от тестирующей системы AtForces, чтобы узнать задачи с предстоящего контеста. Чтобы достичь этого, он пробрался в кабинет администратора и украл листочек, на котором записан список из \(n\) паролей — строк, состоящих из строчных букв латинского алфавита.

Хакер вернулся домой и начал готовиться ко взлому. Он обнаружил, что в системе содержатся только пароли с украденного листочка, и что система определяет эквивалентность паролей \(a\) и \(b\) следующим образом:

• два пароля \(a\) и \(b\) эквивалентны, если существует символ, который есть и в \(a\), и в \(b\);
• два пароля \(a\) и \(b\) эквивалентны, если существует другой пароль \(c\) из списка, которому эквивалентны одновременно и \(a\), и \(b\).

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

К примеру, если в списке содержатся пароли «a», «b», «ab», «d», то с точки зрения системы пароли «a», «b», «ab» эквивалентны друг другу, а пароль «d» никакому другому не эквивалентен. Иначе говоря, если:

• установленный пароль равен, например, «b», то можно зайти в систему под любым из трёх паролей: «a», «b», «ab»;
• установленный пароль равен «d», то можно зайти в систему только под паролем «d».

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

В линию было расположено \(n\) ламп, пронумерованных целыми числами от \(1\) до \(n\). Каждая лампа изначально либо выключена (\(0\)) или включена (\(1\)).

Вам дано \(k\) подмножеств \(A_1, \ldots, A_k\) множества ламп \(\{1, 2, \dots, n\}\), таких что пересечение любых трех подмножеств пусто. Другими словами, для всех \(1 \le i_1 < i_2 < i_3 \le k\) выполнено \(A_{i_1} \cap A_{i_2} \cap A_{i_3} = \varnothing\).

За одну операцию вы можете выбрать одно из этих \(k\) подмножеств и изменить состояние всех ламп из этого подмножества (выключенные лампы становятся включенными, включенные становятся выключенными). Гарантируется, что для данных подмножеств можно совершить несколько операций так, чтобы все лампы стали включенными.

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

Посчитайте \(m_i\) для всех \(1 \le i \le n\).

Маленький Петя очень любит играть. Больше всего он любит играть в игру «Лунки». Это игра для одного игрока со следующими правилами:

Есть N лунок, расположенных в ряд, пронумерованных слева направо числами от 1 до N. У каждой лунки изначально установлена своя сила выброса (у лунки с номером i она равна a_i). Если вбросить шарик в лунку i, то он тут же вылетит из нее и попадет в лунку i + a_i, после чего он опять вылетит и т.д.. Если же лунки с таким номером нету, то он просто вылетит за край ряда. На каждом из M ходов игрок выбирает одно из двух действий:

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

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

Курони плохо разбирается в экономике. Поэтому он решил основать новую финансовую пирамиду под названием Антихайп. У него есть следующие правила:

• Вы можете присоединиться к пирамиде бесплатно и получить \(0\) монет.
• Если вы уже являетесь участником Антихайпа, вы можете пригласить своего друга, который в настоящее время не является участником Антихайпа, и получить количество монет, равное вашему возрасту (за каждого приглашенного друга).

\(n\) людей недавно услышали об Антихайпе, возраст \(i\)-го человека - \(a_i\). Некоторые из них являются друзьями, но дружба сегодня  — странная вещь: \(i\)-й человек является другом \(j\)-го человека тогда и только тогда, когда \(a_i \text{ AND } a_j = 0\), где \(\text{AND}\) обозначает операцию побитового И.

На данный момент никто из \(n\) людей не является членом Антихайпа. Они хотят сотрудничать, чтобы присоединяться и приглашать друг друга в Антихайп таким образом, чтобы максимизировать их суммарную прибыль. Не могли бы вы помочь им?

Слово \(s\) длины \(n\) называется \(k\)-полным, если

• \(s\) — палиндром, то есть \(s_i=s_{n+1-i}\) для всех \(1 \le i \le n\);
• \(s\) имеет период \(k\), то есть \(s_i=s_{k+i}\) для всех \(1 \le i \le n-k\).

Например, «abaaba» — это \(3\)-полное слово, а «abccba» нет.

Бобу вручили слово \(s\) длины \(n\), состоящее только из строчных букв латинского алфавита, и целое число \(k\) такое, что \(n\) делится на \(k\). Он хочет превратить слово \(s\) в любое \(k\)-полное слово.

Для этого Боб может выбирать некоторую позицию \(i\) (\(1 \le i \le n\)) и заменять букву на позиции \(i\) на любую другую строчную букву латинского алфавита.

Поэтому теперь Боба интересует минимальное количество позиций, буквы на которых ему необходимо заменить, чтобы превратить \(s\) в любое \(k\)-полное слово.

Обратите внимание, что Боб может сделать ноль изменений, если слово \(s\) уже \(k\)-полное.

Требуется ответить на \(t\) независимых наборов входных данных.

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

У вас есть таблица размером \(n\times m\). Изначально вы можете поставить несколько магнитов с северным полюсом и несколько магнитов с южным полюсом в некоторые клетки этой таблицы. Вам разрешено расставлять сколько угодно магнитов, в том числе несколько в одну клетку.

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

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

1. В каждой строке и каждом столбце таблицы находится хотя бы один магнит с южным полюсом.
2. Если клетка таблицы черная, тогда можно переместить какой-нибудь магнит с северным полюсом в эту клетку с помощью некоторой последовательности операций из начального расположения магнитов.
3. Если клетка таблицы белая, тогда никакой магнит с северным полюсом невозможно переместить в эту клетку с помощью некоторой последовательности операций из начального расположения магнитов.

Определите, можно ли расположить магниты в таблице так, что все условия будут выполнены. Если это возможно, найдите минимальное количество магнитов с северным полюсом, которое для этого требуется (минимизировать количество магнитов с южным полюсом не нужно).

Vivek столкнулся с интересной задачей. У него есть лабиринт, который можно описать таблицей \(n \times m\). Каждая клетка может быть одного из следующих типов:

• Пустая — '.'
• Стена — '#'
• Хороший человек  — 'G'
• Плохой человек — 'B'

Единственный выход из лабиринта находится в клетке \((n, m)\).

Человек может перейти в клетку если она не содержит стену и она имеет общую сторону с его текущей клеткой. Vivek хочет заблокировать (заменить на стены) некоторые пустые клетки, чтобы все хорошие люди могли дойти до выхода из лабиринта, но чтобы все плохие люди не могли. Клетку которая исходно содержит 'G' или 'B' нельзя блокировать, но через нее можно проходить.

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

Гарантируется, что клетка \((n,m)\) пустая. Vivek разрешается ее блокировать.

У вас есть \(n\) дисков, радиус \(i\)-го диска равен \(i\). Изначально эти диски распределены по \(m\) башням из дисков: каждая башня содержит хотя бы один диск, и диски в каждой башне отсортированы от большего к меньшему снизу вверх.

Вы должны собрать все диски в одну башню. Чтобы сделать это, вы можете выбрать две различных башни \(i\) и \(j\) (каждая из которых содержит хотя бы один диск), взять несколько (возможно, все) верхних дисков с башни \(i\) и поместить их на вершину башни \(j\) в том же самом порядке — при условии, что верхний диск башни \(j\) больше каждого перемещаемого диска. Эту операцию можно применять любое количество раз.

Например, если у вас есть две башни, содержащие диски \([6, 4, 2, 1]\) и \([8, 7, 5, 3]\) (в порядке снизу вверх), существуют ровно две возможные операции:

• переместить диск \(1\) с первой башни на вторую, после чего башни станут следующими: \([6, 4, 2]\) и \([8, 7, 5, 3, 1]\);
• переместить диски \([2, 1]\) с первой башни на вторую, после чего башни станут следующими: \([6, 4]\) и \([8, 7, 5, 3, 2, 1]\).

Пусть сложность некоторого набора башен — это минимальное количество операций, необходимых для того, чтобы собрать все диски в одну башню. Например, сложность набора башен \([[3, 1], [2]]\) равна \(2\): вы можете переместить диск \(1\) на вторую башню, а потом переместить оба диска со второй башни на первую башню.

Вам заданы \(m - 1\) запросов. Каждый запрос обозначается двумя числами \(a_i\) и \(b_i\), обозначающими следующее: «слить башни \(a_i\) и \(b_i\) в одну» (то есть взять все диски из этих башен и составить из них одну башню, в которой диски отсортированы по убыванию размера снизу вверх). Новая башня (являющаяся результатом слияния) получает индекс \(a_i\).

Для каждого \(k \in [0, m - 1]\) посчитайте сложность набора башен после выполнения первых \(k\) запросов.

Вам дана таблица \(a\) размера \(2 \times n\) (из двух строк и \(n\) столбцов), состоящая из целых чисел от \(1\) до \(n\).

За один ход вы можете выбрать какой-то столбец \(j\) (\(1 \le j \le n\)) и обменять местами значения \(a_{1, j}\) и \(a_{2, j}\). Каждый столбец может быть выбран не более одного раза.

Ваша задача — найти минимальное количество ходов, необходимое для того, чтобы получить перестановки размера \(n\) в первой и во второй строках, или же определить, что это сделать невозможно.

Вам необходимо ответить на \(t\) независимых наборов тестовых данных.

Напомним, что перестановкой размера \(n\) называется такой массив размера \(n\), который содержит каждое целое число от \(1\) до \(n\) ровно один раз (порядок элементов не важен).

Поликарп играет в (очередную) стратегическую компьютерную игру. В этой игре он управляет армией наемников.

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

\(i\)-го наемника можно выбрать только в том случае, если итоговое количество выбранных наемников не менее \(l_i\) (иначе этот наемник считает задание слишком опасным) и не более \(r_i\) (он не хочет делить добычу со слишком большим количеством других наемников). Кроме того, \(m\) пар наемников ненавидят друг друга, и из каждой такой пары можно взять на задание не более одного наемника.

Сколько непустых подмножеств наемников Поликарп должен рассмотреть? Другими словами, посчитайте количество подмножеств наемников, которые не содержат пар наемников, ненавидящих друг друга, и размер которых принадлежит отрезку \([l_i, r_i]\) для каждого наемника из подмножества.

Ответ может быть очень большим, поэтому посчитайте его по модулю \(998244353\).

Вам дано \(m\) множеств \(A_1, A_2, \ldots, A_m\), состоящих из целых чисел; элементы этих множеств — целые числа от \(1\) до \(n\) включительно.

Есть два массива положительных целых чисел \(a_1, a_2, \ldots, a_m\) и \(b_1, b_2, \ldots, b_n\).

За одну операцию вы можете удалить элемент \(j\) из множества \(A_i\) и заплатить за это \(a_i + b_j\) монет.

Вы можете сделать несколько (возможно, ноль) операций (после этого некоторые множества могут стать пустыми).

После этого вы построите неориентированный граф, где каждое ребро будет иметь цвет. Граф будет иметь \(n\) вершин. Для каждого множества \(A_i\) вы добавите ребро \((x, y)\) цвета \(i\) для всех \(x, y \in A_i\) и \(x < y\). Некоторые пары вершин могут быть соединены больше чем одним ребром, но такие ребра будут иметь разные цвета.

Мы называем цикл \(i_1 \to e_1 \to i_2 \to e_2 \to \ldots \to i_k \to e_k \to i_1\) (\(e_j\) это какое-то ребро, соединяющее вершины \(i_j\) и \(i_{j+1}\) этого графа) разноцветным, если цвета всех ребер этого цикла различны.

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

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

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

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

И тут герои задумались: какие же дорожки им надо расчистить?

Вам дан неориентированный граф из \(n\) вершин и \(m\) ребер. Изначально в каждой вершине записано число: в вершине \(i\) записано число \(p_i\) (все \(p_i\) — различные числа от \(1\) до \(n\)).

Вы должны обработать \(q\) запросов двух типов:

• \(1\) \(v\) — среди всех вершин, достижимых из вершины \(v\) по ребрам (включая саму вершину \(v\)), найти вершину \(u\) с максимальным записанным в ней числом \(p_u\), вывести \(p_u\) и заменить \(p_u\) на \(0\);
• \(2\) \(i\) — удалить \(i\)-е ребро из графа.

Обратите внимание, что в запросе первого типа может возникнуть такая ситуация, что во всех вершинах, достижимых из \(v\), записано число \(0\) — в таком случае вершина \(u\) явно не определена, но так как от выбора конкретной вершины \(u\) ничего не зависит, в ответ на такой запрос можно выбрать любую вершину, достижимую из \(v\), и вывести число, записанное в ней (то есть \(0\)).

In Bubbleland a group of special programming forces gets a top secret job to calculate the number of potentially infected people by a new unknown virus. The state has a population of \(n\) people and every day there is new information about new contacts between people. The job of special programming forces is to calculate how many contacts in the last \(k\) days a given person had.

The new virus has an incubation period of \(k\) days, and after that time people consider as non-infectious. Because the new virus is an extremely dangerous, government mark as suspicious everybody who had direct or indirect contact in the last \(k\) days, independently of the order of contacts.

This virus is very strange, and people can't get durable immunity.

You need to help special programming forces to calculate the number of suspicious people for a given person (number of people who had contact with a given person).

There are 3 given inputs on beginning \(n\) where \(n\) is population, \(q\) number of queries, \(k\) virus incubation time in days. Each query is one of three types:

1. (\(x\), \(y\)) person \(x\) and person \(y\) met that day (\(x \neq y\)).
2. (\(z\)) return the number of people in contact with \(z\), counting himself.
3. The end of the current day moves on to the next day.

Начался новый учебный год, и в университет Берляндии пришли \(n\) новых студентов, которых разбили на \(k\) групп, причем некоторые группы могли оказаться пустыми. Среди студентов есть \(m\) пар знакомых, причём знакомые студенты могут быть как из одной, так и из разных групп.

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

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

Обратите внимание, что команды, на которые Алиca разделит студентов, не обязаны совпадать с группами, в которых учатся участники. Более того, команды могут быть разного размера (или даже пустыми).

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

В своем плохом сне, у Евклида был набор \(S\) из \(n\) \(m\)-мерных векторов над полем \(\mathbb{Z}_2\), и он мог их складывать. Другими словами, у него были вектора с \(m\) координатами, каждая координата равнялась либо \(0\), либо \(1\). Сложение векторов определяется следующим образом: пусть \(u+v = w\), тогда \(w_i = (u_i + v_i) \bmod 2\).

Евклид может сложить любое подмножество векторов из \(S\) и сохранить получившийся \(m\)-мерный вектор над \(\mathbb{Z}_2\). В частности, он может сложить пустое подмножество векторов. В таком случае, все координаты получившегося вектора будут равны \(0\).

Пусть \(T\) будет множеством всех векторов, которые могут быть получены как сумма некоторого подмножества векторов из \(S\). Теперь Евклид интересуется, каков размер \(T\), и может ли он использовать только какое-то подмножество \(S'\) множества \(S\), чтобы получить все вектора из \(T\). Как всегда и бывает в таких ситуациях, он не проснется до тех пор, пока не выяснит это. Пока что дела для философа обстоят довольно мрачно. Однако, появилась надежда, когда он заметил, что все вектора из \(S\) содержат максимум \(2\) координаты, равные \(1\).

Помогите Евклиду вычислить \(|T|\), количество \(m\)-мерных векторов над \(\mathbb{Z}_2\), которые могут быть получены как сумма какого-то подмножества векторов из \(S\). Так как оно может быть довольно велико, выведите его по модулю \(10^9+7\). Также, вы должны найти \(S'\), минимальное такое подмножество \(S\), что все вектора из \(T\) могут быть получены как как сумма какого-то подмножества векторов из \(S'\). В случае, если существует несколько таких подмножеств с минимальным количеством элементов, выведите лексикографически минимальный по индексам взятых элементов.

Рассмотрим два множества \(A\) и \(B\), такие что \(|A| = |B|\). Пусть \(a_1, a_2, \dots a_{|A|}\) и \(b_1, b_2, \dots b_{|B|}\) будут возрастающие массивы индексов элементов, взятых в \(A\) и в \(B\), соответственно. \(A\) лексикографически меньше, чем \(B\), если существует такое \(i\), что \(a_j = b_j\) для всех \(j < i\) и \(a_i < b_i\).

There are \(n\) cities and \(m\) bidirectional roads in Berland. The \(i\)-th road connects the cities \(x_i\) and \(y_i\), and has the speed limit \(s_i\). The road network allows everyone to get from any city to any other city.

The Berland Transport Ministry is planning a road reform.

First of all, maintaining all \(m\) roads is too costly, so \(m - (n - 1)\) roads will be demolished in such a way that the remaining \((n - 1)\) roads still allow to get to any city from any other city. Formally, the remaining roads should represent an undirected tree.

Secondly, the speed limits on the remaining roads might be changed. The changes will be done sequentially, each change is either increasing the speed limit on some road by \(1\), or decreasing it by \(1\). Since changing the speed limit requires a lot of work, the Ministry wants to minimize the number of changes.

The goal of the Ministry is to have a road network of \((n - 1)\) roads with the maximum speed limit over all roads equal to exactly \(k\). They assigned you the task of calculating the minimum number of speed limit changes they have to perform so the road network meets their requirements.

For example, suppose the initial map of Berland looks like that, and \(k = 7\):

Then one of the optimal courses of action is to demolish the roads \(1\)–\(4\) and \(3\)–\(4\), and then decrease the speed limit on the road \(2\)–\(3\) by \(1\), so the resulting road network looks like that:

У Аркадия есть плейлист, в котором изначально \(n\) песен, пронумерованных от \(1\) до \(n\) в том порядке, в котором они находятся в плейлисте. Аркадий начинает слушать песни из плейлиста друг за другом, начиная с песни \(1\). Плейлист зациклен, то есть после того, как он прослушает последнюю песню, он опять начнет слушать с начала плейлиста.

У каждой песни есть жанр, определяемый натуральным числом \(a_i\). Пусть Аркадий только что прослушал песню с жанром \(y\), а до нее — песню с жанром \(x\). Если \(\operatorname{gcd}(x, y) = 1\), он думает, что песни не сочетаются, и удаляет последнюю прослушанную песню (с жанром \(y\)) из плейлиста. После этого он продолжает слушать песни как обычно, пропуская уже удаленные, при этом он забывает, что слушал какие-то песни до удаления. Иными словами, он не может удалить песню сразу после того, как удалил предыдущую. Здесь \(\operatorname{gcd}(x, y)\) обозначает наибольший общий делитель (НОД) чисел \(x\) и \(y\).

Например, если жанры песен в начальном плейлисте равны \([5, 9, 2, 10, 15]\), то прослушивание происходит следующим образом: [5, 9, 2, 10, 15] \(\to\) [5, 9, 2, 10, 15] \(\to\) [5, 2, 10, 15] (т. к. \(\operatorname{gcd}(5, 9) = 1\)) \(\to\) [5, 2, 10, 15] \(\to\) [5, 2, 10, 15] \(\to\) [5, 2, 10, 15] \(\to\) [5, 2, 10, 15] \(\to\) [5, 2, 10, 15] \(\to\) [5, 10, 15] (т. к. \(\operatorname{gcd}(5, 2) = 1\)) \(\to\) [5, 10, 15] \(\to\) [5, 10, 15] \(\to\) ... Жирным выделены последние две прослушанные песни. Обратите внимание, после удаления некоторой песни Аркадий забывает, что слушал ее и предыдущую.

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

Как преподаватель, Riko Hakozaki часто помогает ученикам в решении задач по различным предметам. Сегодня ее попросили помочь с задачей по программированию, которая заключается в следующем.

Вам выдается неориентированный полный граф с \(n\) вершинами, где для некоторых ребер заданы положительные веса, а для остальных нет. Вам нужно назначить всем еще не назначенным рёбрам неотрицательные веса так, чтобы у получившегося графа XOR (побитовое исключающее ИЛИ) всех весов был равен \(0\).

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

Напомним, что неориентированный полный граф с \(n\) вершинами содержит все рёбра \((u, v)\) с \(1 \le u < v \le n\); такой граф имеет \(\frac{n(n-1)}{2}\) рёбер.

Она не знает, как решить эту задачу, поэтому просит вас решить ее за нее.

Родина Феникса, Страна Огня, состоит из \(n\) городов, которые были соединены \(m\) дорогами, но из-за землетрясения они все были разрушены. Теперь Страна Огня хочет восстановить \(n-1\) из этих дорог так, чтобы все города стали снова связаны.

Первоначально, в \(i\)-м городе есть \(a_i\) тонн асфальта. Чтобы восстановить дорогу, необходимо \(x\) тонн асфальта. При этом, чтобы восстановить дорогу между городами \(i\) и \(j\), в городах \(i\) и \(j\) должно быть суммарно хотя бы \(x\) тонн асфальта. Другими словами, в городе \(i\) есть \(a_i\) тонн асфальта, а городе \(j\) — \(a_j\) тонн, то после восстановления дороги между ними останется \(a_i+a_j-x\) тонн. Асфальт можно перевозить между городами, если дорога между ними уже восстановлена.

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

Во время перерывов в подготовке к Международной олимпиаде школьников по информатике маленький Алан любит решать различные головоломки, чтобы развивать мозги. Сегодня он решает головоломку, которая выглядит как таблица \(2 \times n\), где в каждом ряду записана перестановка чисел \(1,2,3,\ldots,n\).

Задача головоломки — сделать так, чтобы ни в каком ряду и ни в каком столбце не было двух одинаковых чисел (назовем такие состояния решенными), а единственная разрешенная операция — поменять местами два числа в одном столбце. Когда маленький Алан решил головоломку много раз, он заскучал и начал размышлять, а сколько вообще существует различных решенных состояний в данной головоломке, которые он может получить из некоторого начального решенного состояния, применяя только разрешенные операции?

Маленький Алан не справился с этой сложной задачей, поэтому он попросил вас помочь ему. Найдите ответ по модулю \(10^9+7\).

Представьте себе бесконечный пруд, спроецированный на числовую прямую. В пруду есть \(n\) камней, пронумерованных от \(1\) до \(n\). \(i\)-й камень находится в целой координате \(a_i\). Координаты камней попарно различны. Камни пронумерованы в порядке увеличения координаты, поэтому \(a_1 < a_2 < \dots < a_n\).

Лягушка-робот сидит на камне номер \(s\). Лягушку можно запрограммировать. У нее есть встроенный параметр базовой длины прыжка \(d\). Также есть настройка для интервала длины прыжка. Если интервал длины прыжка выставляется на некоторое целое значение \(k\), то лягушка может прыгать с некоторого камня на любой другой камень на расстоянии от \(d - k\) до \(d + k\) включительно в любом направлении. Расстояние между двумя камнями — это модуль разности между их координатами.

Вам поручили задачу реализовать новую функцию для лягушки. По двум заданным целым числам \(i\) и \(k\) определить, может ли лягушка достичь камня номер \(i\) с камня номер \(s\), осуществив последовательность прыжков с интервалом длины прыжка установленным на \(k\). Последовательность может быть сколь угодно длинной или пустой.

Вам будет предоставлено \(q\) тестов для данной функции, \(j\)-й набор состоит из двух целых чисел \(i\) и \(k\). Выведите «Yes», если \(i\)-й камень достижим и «No» в противном случае.

Вы можете выводить «YES» и «NO» в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).

Рассмотрим последовательность различных целых чисел \(a_1, \ldots, a_n\), каждое из которых соответствует отдельной вершине графа. Будем соединять две вершины ребром, если соответствующие им числа не взаимно просты, т. е. если они имеют общий делитель, больший чем \(1\).

Вам даны \(q\) запросов, в каждом запросе вы хотите попасть из вершины, соответствующей значению \(a_s\), в вершину, соответствующую \(a_t\). Для того чтобы это сделать, вы можете выбирать существующее значение \(a_i\), создать новую вершину со значением \(a_{n+1} = a_i \cdot (1 + a_i)\) и соединить ее со всеми вершинами, значения которых не взаимно просты с \(a_{n+1}\). После этого \(n\) увеличивается на \(1\). Вы можете повторять эту операцию любое количество раз, удлиняя последовательность, и, возможно, получая одинаковые значения. Какое минимальное количество вершин нужно добавить, чтобы \(a_t\) стало достижимо из \(a_s\)?

Обратите внимание, что запросы независимы. В каждом запросе вы начинаете с исходной последовательности \(a\), заданной во входных данных.

Как уже упоминалось, Василий любит играть в компьютерные игры. В одной из его любимых игр персонаж находится во вселенной, где каждая планета обозначается двоичным числом от \(0\) до \(2^n - 1\). На каждой из планет находятся врата, позволяющие перемещаться с планеты \(i\) на планету \(j\), если двоичная запись \(i\) отличается от двоичной записи \(j\) ровно в одном бите.

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

• Уничтожить планеты с номерами от \(l\) до \(r\) включительно. На такие планеты больше нельзя перемещаться.
• Узнать, можно ли с планеты \(a\) долететь до планеты \(b\), используя какое-то количество планетных врат. Гарантируется, что планеты \(a\) и \(b\) не являются уничтоженными.