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

Известно, что из столицы (город с номером \(1\)) можно добраться до любого другого города, перемещаясь по дорогам.

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

• из столицы будет возможно добраться до любого другого города по выбранной \(n-1\) дороге,
• пусть \(d_i\) — количество дорог, сколько придется преодолеть на пути из столицы в город \(i\), двигаясь только по выбранной \(n-1\) дороге, тогда \(d_1 + d_2 + \dots + d_n\) — должно быть минимально.

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

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

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

Януш — бизнесмен. Он владеет компанией «Янушзекс», которая производит игры для школьников. Последним хитом Янушзекс является крутая игра для одного человека «Сделай единицу». Игроку дана последовательность из \(n\) целых чисел \(a_i\).

Разрешается выбрать любое подмножество из них и количество очков равно наибольшему общему делителю выбранных чисел. Игроку нужно выбрать наименьшее количество элементов, получив количество очков, равное \(1\). Теперь Януш интересуется, какое минимальное количество элементов нужно выбрать игроку в таком случае?

В одном из уровней компьютерной игры вы попали в лабиринт, состоящий из n строк, каждая из которых содержит m клеток. Каждая клетка либо свободна, либо занята препятствием. Стартовая клетка находится в строке r и столбце c. За один шаг вы можете переместиться на одну клетку вверх, влево, вниз или вправо, если она не занята препятствием. Вы не можете перемещаться за границы лабиринта.

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

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

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

Определим \(k\)-мультиёж следующим образом:

• \(1\)-мультиёж — это ёж: одна вершина степени хотя бы \(3\) и несколько вершин степени 1.
• Для всех \(k \ge 2\), \(k\)-мультиёж — это \((k-1)\)-мультиёж, для каждой висячей вершины \(v\) которого проделали следующие операции: пусть \(u\) — её единственный сосед, удалим вершину \(v\), создадим новый ёж с центром в вершине \(w\), соединим ребром вершины \(u\) и \(w\). Новые ежи могут отличаться как друг от друга, так и от подаренного Ване.

Таким образом, \(k\)-мультиёж является деревом. Ваня сделал \(k\)-мультиёж, но не уверен, что нигде не ошибся, поэтому попросил вас проверить, является ли созданное им дерево \(k\)-мультиежом.

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

Требуется удалить несколько ребер графа так, чтобы осталось не более \(k\) ребер. Назовем вершину \(i\) хорошей, если после удаления ребер все еще существует путь из \(1\) в \(i\) длины \(d_i\).

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

Килани играет в игру со своими друзьями. Игра представляет из себя клетчатое поле размером \(n \times m\), где каждая клетка или пуста, или заблокирована, также у каждого игрока есть один или несколько замков на поле (ни одна клетка не содержит более одного замка).

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

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

Вам дан неориентированный граф специального вида. Он состоит из \(2n\) вершин, пронумерованных от \(1\) до \(2n\). Граф обладает следующими свойствами:

• в нем ровно \(3n-2\) ребра: \(n\) ребер соединяют вершины с четными номерами и вершины с нечетными номерами, \(n - 1\) ребер соединяют вершины с нечетными номерами друг с другом, и \(n - 1\) ребер соединяют вершины с четными номерами друг с другом;
• для каждого ребра \((u, v)\) между вершинами с нечетными номерами существует ребро \((u + 1, v + 1)\), и наоборот;
• для каждого нечетного числа \(u \in [1, 2n - 1]\) существует ребро \((u, u + 1)\);
• граф является связным; более того, если мы удалим все четные вершины и ребра, инцидентные им, граф станет деревом (то же самое произойдет, если удалить все нечетные вершины).

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

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

Вам даны \(q\) запросов к графу; в каждом запросе требуется подсчитать длину кратчайшего пути между какой-то парой вершин. Можете ли вы справиться со всеми запросами?

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

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

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

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

Благодаря помощи Доктора, повстанцам удалось украсть достаточно золота, чтобы запустить полномасштабную атаку на эмперию! Однако Дарт Вейдер ищет возможности отомстить и забрать назад своё золото.

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

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

Всего у империи есть \(s\) космических кораблей, а у повстанцев есть \(b\) баз, расположенных на различных планетах галактики.

У каждого космического корабля есть его местоположение \(x\), обозначающее индекс планеты, на которой он находится, его сила атаки \(a\) и определённый уровень топлива \(f\).

У каждой базы есть местоположение \(x\) и уровень защиты \(d\).

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

• Сила атаки космического корабля больше или равна уровня защиты базы,
• Уровень топлива космического корабля больше или равен кратчайшему расстоянию (количество червоточин) между планетой космического корабля и планетой с базой

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

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

Таким образом, для каждой атакованной базы повстанцы теряют по \(k\) золота.

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

Разумеется, фейковые базы не содержат золота, но создание одной такой базы стоит \(h\) золота.

Какое минимальное количество золота повстанцы потеряют, если они создадут оптимальное количество фейковых баз?

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

Вашей задачей является вычисление функции \(E_{max}(c)\), которая определена также как и в лёгкой версии — как наибольшее \(e \le 10^9\), такое что если мы изменим энергию коридора \(c\) на \(e\), то Далеки могут им воспользоваться. Однако теперь эту функцию нужно вычислить для каждого коридора, который Хайди рассматривает.

В магазине неподалеку продаются известные русские деревянные игрушки под названием «матрешки», и вы бы хотели приобрести несколько штук. В магазине продается \(n\) различных матрешек. Любая матрешка — это фигурка объема \(out_i\) с пустотой внутри объемом \(in_i\) (конечно, \(out_i > in_i\)).

У вас не так много свободного места в сумке, но, к счастью, вы знаете, что матрешки можно вкладывать друг в друга. Формально, назовем набор матрешек вкладываемым, если мы можем переупорядочить их таким образом, что первая матрешка вкладывается во вторую, вторая — в третью и так далее. Матрешка \(i\) вкладывается в матрешку \(j\), если \(out_i \le in_j\). Только последняя игрушка из вкладываемого набора будет занимать место в вашей сумке.

Назовем пустотой вкладываемого набора общий объем пустого места внутри данной структуры. Очевидно, что она равна \(in_{i_1} + (in_{i_2} - out_{i_1}) + (in_{i_3} - out_{i_2}) + \dots + (in_{i_k} - out_{i_{k-1}})\), где \(i_1\), \(i_2\), ..., \(i_k\) — индексы выбранных матрешек в порядке их вкладывания.

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

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

Так как ответ может быть очень большим — выведите его по модулю \(10^9 + 7\).

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

Алиса и Боб играют в игру на шахматной доске размера \(n \times m\), где \(n\) и \(m\) являются чётными числами. Ряды доски пронумерованы целыми числами от \(1\) до \(n\), а столбцы пронумерованы от \(1\) до \(m\). На доске расположены два коня — белый и чёрный. Белый изначально находится в клетке \((x_1, y_1)\), а чёрный — в клетке \((x_2, y_2)\). Алиса выбирает коня, которым будет играть сама, а Боб будет играть другим.

Алиса и Боб будут делать ходы по очереди. Тот, кто играет белым конём, начинает игру. За один ход каждый игрок должен передвинуть своего коня в соответствии с шахматными правилами. А именно, если сейчас конь находится в клетке \((x, y)\), то его можно передвинуть в любую из следующих клеток (в предположении, что они находятся в пределах шахматной доски):

Общеизвестно, что конь имеет наибольшую силу в центре доски. Для обоих коней известна клетка, в которую тот хочет попасть:

• владелец белого коня выиграет, если он возьмет чёрного коня, или если белый конь окажется в клетке \((n/2, m/2)\), которую в этот момент не бьёт черный конь;
• владелец чёрного коня выигрывает, если он возьмет белого коня, или если чёрный конь окажется в клетке \((n/2+1, m/2)\), которую в этот момент не бьёт белый конь.

Формально, игрок, взявший другого коня, выигрывает. Кроме того, игрок, находящийся в требуемой позиции (\((n/2, m/2)\) для белого коня, \((n/2+1, m/2)\) для чёрного коня) не под боем оппонента, выигрывает.

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

Если Алиса сделала \(350\) ходов и никто не выиграл, игра заканчивается вничью.

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

Взаимодействие начинается с двух целых чисел \(n\) и \(m\) (\(6 \le n,m \le 1000\), \(n\) и \(m\) чётные) — размеров доски.

Вторая строка содержит четыре целых числа \(x_1, y_1, x_2, y_2\) (\(1 \le x_1, x_2 \le n\), \(1 \le y_1, y_2 \le m\)) — клетки, в которых расположен белый и чёрный конь. Гарантируется, что два коня находятся в разных клетках. Также гарантируется, что ни один из коней сейчас не находится в своей требуемой клетке (однако он может находится в требуемой клетке своего соперника).

Ваша программа должна ответить «WHITE» или «BLACK» в зависимости от того, каким конём она хочет играть. В случае, если вы выберете белого коня, вы начинаете игру.

В течении каждого своего хода вы должны вывести два целых числа: \(x\) и \(y\) — координаты клетки, в которую вы хотите переместить своего коня. Если вы выиграли игру этим ходом, вы должны немедленно завершить свою программу.

После каждого хода оппонента вы получите два целых числа: \(x\) и \(y\) — координаты клетки, куда Боб переместил своего коня.

Если ваш последний ход был некорректен или вы проиграли игру в результате хода программы жюри, или если вы сделали \(350\) ходов и всё ещё не выиграли, вы получите «-1 -1». В таких случаях, немедленно завершите вашу программу, чтобы получить вердикт Неправильный ответ.

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

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

Взломы в этой задаче отключены.

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

Главные герои были опущены для краткости.

Вам дан ориентированный невзвешенный граф без петель с \(n\) вершинами и путь в нём (не обязательно простой), заданный последовательностью \(p_1, p_2, \ldots, p_m\) из \(m\) вершин; для любого \(1 \leq i < m\) существует дуга из \(p_i\) в \(p_{i+1}\).

Будем называть последовательность \(v_1, v_2, \ldots, v_k\) из \(k\) вершин хорошей, если \(v\) является подпоследовательностью \(p\), \(v_1 = p_1\), \(v_k = p_m\), и \(p\) является одним из кратчайших путей, проходящих через вершины \(v_1\), \(\ldots\), \(v_k\) в этом порядке.

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

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

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

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

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

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

Представим лес Берляндии как бесконечное клеточное поле. В каждой клетке растет дерево. Или росло, до недавних событий.

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

Пожарные быстро потушили огонь, и теперь расследуют данный инцидент. Основная версия — это поджог: в какой-то момент времени (примем этот момент за \(0\)) несколько деревьев были подожжены. В начале минуты \(0\) горели только подожженные деревья. В конце каждой минуты огонь распространяется от горящего дерева к \(8\) соседним к нему деревьям. В начале минуты \(T\) огонь был потушен.

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

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

Хиякугоку недавно покинула должность местного божежства Южного Храма Черной Улитки в погоне за своей мечтой стать художником мультфильмов. Шесть месяцев она только и делала, что играла в веревочку («Cat's Cradle»), и теперь решила попробовать новую игру — «Змеи и лестницы» («Лила»). К сожалению, все змеи оказались истреблены, поэтому остались лишь только лестницы.

Игра происходит на доске \(10 \times 10\) по следующим правилам:

• В начале игры игрок стоит в левой нижней клетке.
• Цель игры заключается в достижении игроком финиша (левой верхней клетки). Как только он достигает финиша, игра заканчивается.
• Путь выглядит следующим образом: если клетка находится не на краю ряда, то она ведет в следующую клетку по направлению движения ряда; если на краю, то ведет в ячейку выше. Направление движение ряда определяется так: направление в самом нижнем ряду — направо; направление в любом другом ряду противоположно направлению предыдущего ряда. В примечании есть изображение данного маршрута.
• На каждом ходу игрок бросает стандартный шестигранный кубик. Пусть выпало некоторое число \(r\). Если до финиша меньше \(r\) ходов, тогда игрок остается на месте (но ход считается сделанным). Иначе игрок делает ровно \(r\) шагов по своему пути и останавливается. Если игрок остановился в клетке, в которой находится основание лестницы, то игрок может выбрать, залезть по лестнице или нет. Если он выбирает не залезать, то к следующему ходу он остается в этой клетке.
• В некоторых клетках есть лестницы. Лестницы расположены только вертикально — каждая ведет в ту же клетку в одном из рядов сверху.Игрок обязан остановиться в клетке, содержащей основание лестницы, после броска кубика, чтобы иметь возможность забраться по данной лестнице. После использования лестницы игрок оказывается в клетке, содержащей верхний конец лестницы. Нельзя слезть с лестницы в ходе восхождения. И если клетка, содержащая верхний конец лестницы, содержит также и основание другой лестницы, то вторую лестницу использовать нельзя.
• Числа, написанные на кубике: 1, 2, 3, 4, 5 и 6 — у каждого одинаковая вероятность выпасть.

Обратите внимание, что:

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

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

The director of the famous dance show plans a tour. It is already decided that the tour will consist of up to \(m\) concerts.

There are \(n\) dancers in the troupe. Each dancer is characterized by her awkwardness: the awkwardness of the \(i\)-th dancer is equal to \(a_i\).

The director likes diversity. For this reason, each concert will be performed by a different set of dancers. A dancer may perform in multiple concerts. For example, it is possible that a set of dancers performs in one concert and a subset of this set of dancers performs in another concert. The only constraint is that the same set of dancers cannot perform twice.

The director prefers the set with larger number of dancers over the set with smaller number of dancers. If two sets consist of the same number of dancers, then the director prefers the one which has smaller sum of awkwardness of dancers. If two sets of dancers are equal in size and total awkwardness, then the director does not have a preference which one is better.

A marketing study shows that viewers are not ready to come to a concert if the total awkwardness of all the dancers performing in the concert is greater than \(k\).

The director wants to find the best plan for \(m\) concerts. He thinks to write down all possible sets of dancers; then get rid of the sets with total awkwardness greater than \(k\). The remaining sets of dancers will be sorted according to his preference. The most preferred set of dancers will give the first concert, the second preferred set — the second concert and so on until the \(m\)-th concert. If it turns out that the total number of valid sets is less than \(m\), then the total number of concerts will be equal to the number of valid sets.

It turns out that the director delegated finding the plan to you! Please, notice that there might be several acceptable plans due to the fact that the director does not have a preference over sets of dancers with the same size and total awkwardness. In this case any of these plans is good enough. For each concert find the number of dancers and the total awkwardness of the set performing. Also, for the last concert find its set of dancers.

Вам задан массив \(a\), состоящий из \(n\) целых чисел. За один ход вы можете прыгнуть с позиции \(i\) в позицию \(i - a_i\) (если \(1 \le i - a_i\)) или в позицию \(i + a_i\) (если \(i + a_i \le n\)).

Для каждой позиции \(i\) от \(1\) до \(n\) вы хотите узнать минимальное количество ходов, необходимое, чтобы достичь любой позиции \(j\) такой, что \(a_j\) имеет четность, отличающуюся от четности \(a_i\) (то есть если \(a_i\) нечетно, то \(a_j\) должно быть четным и наоборот).

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

Джабер дал каждому городу в стране свой цвет от \(1\) до \(k\). За одну секунду он может пройти из текущего города в любой соседний по стороне город или в любой город, с таким же цветом, как цвет текущего города.

Джабер должен выполнить \(q\) миссий. В каждой миссии он начинает в городе в строке \(r_1\) и столбце \(c_1\) и должен помочь кому-то в городе в строке \(r_2\) и столбце \(c_2\).

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

Бесси пасется на ферме, состоящей из \(n\) полей, соединенных с помощью \(m\) двусторонних дорог. Сейчас она находится на поле \(1\), и вернется домой на поле \(n\) в конце дня.

Кор-федерация Коровников приказала Фермеру Джону построить одну дополнительную двустороннюю дорогу. У фермы есть \(k\) особых полей, и было решено построить дорогу между двумя различными особыми полями. Фермер Джон может построить дорогу даже между полями, которые уже соединены дорогой.

Уже после постройки дороги, Бесси вернется по кратчайшему пути от поля \(1\) к полю \(n\). Так как Бесси нужно больше тренироваться, Фермер Джон должен максимизировать длину данного кратчайшего пути. Помогите ему!

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

Последовательность \(a\) является подпоследовательностью массива \(b\), если \(a\) можно получить из \(b\), удалив несколько (возможно, ноль или все) элементов.

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

Майк планирует совершить путешествие из вершины (района) \(a\) в вершину (район) \(b\), а затем из вершины (района) \(b\) в вершину (район) \(c\). Он может посещать один и тот же район дважды или даже большее число раз. Но есть небольшая проблема: власти города хотят ввести цену за использование дорог, таким образом, что если кто-то проходит по ней, то он должен заплатить цену, соответствующую этой дороге (он платит каждый раз, когда проходит по дороге). Список используемых цен \(p\) готов и они просто хотят распределить его между всеми дорогами в городе таким образом, что каждая цена из массива соответствует ровно одной дороге.

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

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

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

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

Изначальный полигон для \(n=4\).

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

Более формально:

• если пушка, стоящая в строке \(i\) перед первым столбцом, стреляет единицей, то единица начинает свой полет из клетки (\(i, 1\)) и заканчивает в какой-то клетке (\(i, j\));
• если пушка, стоящая в столбце \(j\) над первой строкой, стреляет единицей, то единица начинает свой полет из клетки (\(1, j\)) и заканчивает в какой-то клетке (\(i, j\)).

Например, рассмотрим следующую последовательность выстрелов:

1. Стреляет пушка в строке \(2\).                         2. Стреляет пушка в строке \(2\).                         3. Стреляет пушка в столбце \(3\).

У вас на столе лежит отчет с проведенных учений. Этот отчет является квадратной матрицей с длиной стороны \(n\), состоящей из нулей и единиц. Вам интересно, действительно ли произошли учения. Другими словами, существует ли такая последовательность выстрелов, что в конце получится заданная матрица?

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

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

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

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

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

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

Более формально, пусть две загаданные вершины это \(s\) и \(f\). За один запрос, вы можете дать множество вершин \(\{a_1, a_2, \ldots, a_c\}\) дерева. В результате вы получите два числа \(a_i\) и \(dist(a_i, s) + dist(a_i, f)\). Вершина \(a_i\) является любой вершиной из данного вами множества, для которой число \(dist(a_i, s) + dist(a_i, f)\) минимально.

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

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

• В начале строки выведите «? c » (без кавычек), где \(c\) \((1 \leq c \leq n)\) равно количеству вершин в списке, про который вы хотите сделать запрос. После этого должны следовать \(c\) различных целых чисел из отрезка \([1, n]\)  — номера вершин из списка.

В ответ на запрос, вы получите два целых числа \(x\), \(d\)  — вершина (из вершин из списка из запроса) с минимальной суммой расстояний до двух загаданных вершин и сумма расстояний от этой вершины до двух загаданных вершин. Если список вершин в запросе некорректный или вы превысили лимит на количество запросов, вы получите \(x = d = -1\). В этом случае, вы должны завершить вашу программу немедленно.

После того, как вы угадаете загаданные вершины, выведите единственную строку «! » (без кавычек). После этого выведите два целых числа из отрезка \([1, n]\)  — загаданные вершины. Вы можете выводить их в любом порядке.

После этого, вы должны считать строку. Если вы угадали вершины правильно, вы получите строку «Correct». В этом случае вы должны продолжить решать оставшиеся наборы входных данных или завершить программу, если все наборы входных данных были решены. Иначе, вы получите строку «Incorrect». В этом случае, вы должны завершить программу немедленно.

Запрос угадывания загаданных вершин не считается в количестве сделанных запросов.

Интерактор не адаптивный. Загаданные вершины не меняются во время запросов.

Не забывайте считать строку «Correct» / «Incorrect» после запроса угадывания вершин.

Вы должны решить набор входных данных перед получением входных данных следующего набора входных данных.

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

После вывода запроса, не забывайте выводить символ переноса строки и сбрасывать буфер выходного потока. Иначе, вы получите вердикт Idleness limit exceeded. Чтобы это сделать, используйте:

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

Взломы

Чтобы сделать взлом, используйте следующий формат теста:

В первой строке должно находиться единственное целое число \(t\) \((1 \leq t \leq 10)\) — количество наборов входных данных. Затем должно следовать описание наборов входных данных.

Первая строка каждого набора входных данных должна содержать единственное целое число \(n\) \((2 \le n \le 1000)\) — количество вершин в дереве. Во второй строке должно находиться два различных целых числа из отрезка \([1, n]\) — загаданные вершины. Следующая \(n - 1\) строка должна содержать по два целых числа \(u\), \(v\) \((1 \le u, v \le n, u \ne v)\) — ребра дерева.

Комитет по Исследованию Двоичных Вирусов открыл способ репродукции широкой семьи вирусов, генетический код которых состоит из нулей и единиц. Каждый вирус возникает из одного гена; для простоты, гены обозначены целыми числами от \(0\) до \(G - 1\). В любой момент времени вирус представляет собой цепочку генов. Когда происходит мутация, один из генов в цепочке заменяется на одну из цепочек генов в соответствии с таблицой мутаций. Вирус прекращает мутировать, когда он состоит только из генов \(0\) и \(1\).

Например, при следующей таблице мутации: \(\) 2 \to \langle 0\ 1 \rangle \\ 3 \to \langle 2\ 0\ 0\rangle\\ 3 \to \langle 1\ 3\rangle\\ 4 \to \langle 0\ 3\ 1\ 2\rangle\\ 5 \to \langle 2\ 1\rangle\\ 5 \to \langle 5\rangle \(\) вирус, который изначально состоял из одного гена \(4\), мог мутировать так: \(\) \langle 4 \rangle \to \langle \underline{0\ 3\ 1\ 2} \rangle \to \langle 0\ \underline{2\ 0\ 0}\ 1\ 2 \rangle \to \langle 0\ \underline{0\ 1}\ 0\ 0\ 1\ 2 \rangle \to \langle 0\ 0\ 1\ 0\ 0\ 1\ \underline{0\ 1} \rangle \(\) или же другим образом: \(\) \langle 4 \rangle \to \langle \underline{0\ 3\ 1\ 2} \rangle \to \langle 0\ \underline{1\ 3}\ 1\ 2 \rangle \to \langle 0\ 1\ 3\ 1\ \underline{0\ 1} \rangle \to \langle 0\ 1\ \underline{2\ 0\ 0}\ 1\ 0\ 1 \rangle \to \langle 0\ 1\ \underline{0\ 1}\ 0\ 0\ 1\ 0\ 1 \rangle \(\)

Вирусы выявляются антителами, которые обнаруживают присутствие конкретных последовательностей нулей и единиц в коде вирусов. Например, антитело, которое реагирует на последовательность \(\langle 0\ 0\ 1\ 0\ 0 \rangle\), обнаружит вирус \(\langle 0\ 0\ 1\ 0\ 0\ 1\ 0\ 1 \rangle\), но не обнаружит вирус \(\langle 0\ 1\ 0\ 1\ 0\ 0\ 1\ 0\ 1 \rangle\).

Для каждого гена от \(2\) до \(G-1\), учёные хотят знать, достаточно ли данного множества антител, чтобы обнаружить все вирусы, которые могут мутировать из этого гена. Если нет, то они хотят знать длину кратчайшего вируса, который невозможно обнаружить.

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

Подзадачи:

1. (11 баллов) Без антител (\(M = 0\))
2. (14 баллов) \(N = G - 2\)
3. (25 баллов) Одно антитело (\(M = 1\))
4. (32 баллов) Сумма всех значений \(\ell\) не превышает \(10\)
5. (18 баллов) Без дополнительных ограничений.

В бутике Карусель вновь кипит работа! Рарити решила посетить бал пони и для этого ей, конечно, необходимо новое платье, ведь выходить в свет в одном и том же платье несколько раз является признаком дурного тона. Для того чтобы сшить платье, ей прежде всего нужна выкройка, которую она вырежет из прямоугольного куска разноцветной ткани.

Кусок разноцветной ткани состоит из \(n \times m\) отдельных квадратных лоскутков. Так как Рарити любит платья со вкусом, выкройка должна быть целиком составлена из лоскутков одного цвета. Выкройка должна быть квадратной и, так как Рарити обожает ромбы, его стороны должны находиться под углом \(45^{\circ}\) к сторонам куска ткани (так он больше всего похож на классическое представление ромба).

Примеры подходящих выкроек: Примеры неподходящих выкроек: Первая состоит из лоскутков разного цвета, вторая выходит за границы куска ткани, третья не является квадратом со сторонами под углом \(45^{\circ}\) к сторонам куска ткани.

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

Егор — известный российский певец, рэпер, актёр и блогер, и наконец-то он решил дать концерт в солнечной республике Дагестан.

В республике есть \(n\) городов, некоторые пары которых соединены \(m\) односторонними дорогами без дополнительных условий. Иными словами, дорожная сеть Дагестана представляет собой произвольный ориентированный граф. Егор собирается прилететь в город \(1\), проехать из него по дорогам вдоль некоторого пути до города \(n\), дать в нём концерт и улететь.

Как и у любого артиста, у Егора есть множество недоброжелателей и слишком назойливых фанатов, поэтому ездить Егор и его команда будут только по безопасным дорогам. В Дагестане есть два типа дорог, чёрные и белые: по чёрным можно безопасно проехать только ночью, а по белым — только утром. Перед началом поездки менеджер Егора составляет расписание: он выбирает для каждого города его тип, чёрный или белый, и если команда посещает какой-то город, то уехать из него она сможет только по одной из дорог соответствующего типа. После определения расписания Егор выбирает любой маршрут из города \(1\) в город \(n\), причём из соображений безопасности этот путь должен быть кратчайшим. Менеджер Егора очень любит Дагестан и хочет задержаться здесь подольше, поэтому он попросил Вас составить такое расписание, чтобы из города \(1\) в город \(n\) не существовало пути вообще, или кратчайший путь был максимально возможной длины.

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

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

Вы и ваш друг играете в Mortal Kombat XI. Вы пытаетесь пройти башню испытаний. Всего в башне есть \(n\) боссов, пронумерованных от \(1\) до \(n\). Тип \(i\)-го босса равен \(a_i\). Если \(i\)-й босс является легким, то его тип равен \(a_i = 0\), иначе этот босс является сложным и его тип равен \(a_i = 1\).

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

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

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

Например: предположим, что \(n = 8\), \(a = [1, 0, 1, 1, 0, 1, 1, 1]\). Тогда лучшей последовательностью действий является следующая:

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

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

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

Давайте расчертим весь город на \(n \times n\) квадратных регионов. Юре нужно добраться из региона с координатами \((s_x,s_y)\) в регион с координатами \((f_x,f_y)\). За одну минуту Юра может переместиться в любой соседний по стороне регион, то есть он может двигаться в четырех направлениях. Также в городе есть \(m\) точек для быстрого перемещения. Их координаты вам (и Юре, конечно) известны. Юра может мгновенно переместиться к точке быстрого перемещения, если сейчас он находится в клетке с той же самой координатой по \(x\) или по \(y\).

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

У Монокарпа было дерево из \(n\) вершин с корнем в вершине \(1\). Он решил изучить алгоритм BFS (Поиск в ширину), и поэтому запустил BFS на своем дереве, стартуя с корня. Упрощенно, BFS можно описать следующим псевдокодом:

a = [] # порядок, в котором вершины обработались
q = Queue()
q.put(1) # кладем корень в конец очереди
while not q.empty():
    k = q.pop() # достаем вершину из начала очереди
    a.append(k) # кладем k в конец последовательности, описывающей порядок посещения вершин
    for y in g[k]: # g[k] — это список всех детей вершины k, отсортированный в порядке возрастания
        q.put(y)

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

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

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

Помогите Монокарпу найти любое дерево с заданным порядком посещения \(a\) и минимальной высотой.

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

В этом обществе доход \(i\)-о человека равен \(a_i\). Человек \(i\) завидует человеку \(j\), если \(a_j=a_i+1\). То есть человек \(j\) имеет ровно на \(1\) больше дохода, чем человек \(i\).

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

Неравенство доходов общества определяется как \(\max\limits_{1 \leq i \leq n} a_i - \min\limits_{1 \leq i \leq n} a_i\).

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

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

Определим вес пути, состоящего из \(k\) ребер с индексами \(e_1, e_2, \dots, e_k\) как \(\sum\limits_{i=1}^{k}{w_{e_i}} - \max\limits_{i=1}^{k}{w_{e_i}} + \min\limits_{i=1}^{k}{w_{e_i}}\), где \(w_i\) — вес \(i\)-го ребра в графе.

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

Дан взвешенный неориентированный граф на \(n\) вершинах, а также \(q\) троек \((u, v, l)\), в каждой из которых \(u\) и \(v\) — некоторые вершины графа, а \(l\) — натуральное число. Назовём ребро \(e\) полезным, если существует хотя бы одна тройка \((u, v, l)\), для которой найдётся путь (не обязательно простой) в графе со следующими свойствами:

• \(u\) и \(v\) являются концами этого пути,
• путь содержит ребро \(e\),
• сумма весов рёбер этого пути не превосходит \(l\).

Найдите количество полезных рёбер в этом графе.

В стране \(n\) городов и \(m\) двунаправленных дорог. Дороги в стране формируют неориентированный взвешенный граф. Граф может быть несвязным. У каждой дороги есть свой параметр \(w\). Вы можете ездить по дорогам, но правительство издало новый закон: вы можете проезжать только по двум дорогам сразу (проехать из города \(a\) в город \(b\), и из города \(b\) в город \(c\)) и вы должны будете заплатить \((w_{ab} + w_{bc})^2\) денег, чтобы проехать по этим дорогам. Для каждого города \(t\) найдите, можно ли добраться до него из города \(1\), и какое наименьшее количество денег необходимо потратить, чтобы добраться из \(1\) в \(t\).

Будем говорить, что остовное дерево некоторого графа является деревом поиска в ширину с корнем в вершине \(s\), если и только если для всех вершин \(t\) кратчайшее расстояние между вершинами \(s\) и \(t\) в графе равно кратчайшему расстоянию между \(s\) и \(t\) в этом остовном дереве.

Для фиксированного графа можно определить \(f(x,y)\) как число остовных деревьев в данном графе таких, что они являются деревьями поиска в ширину как с корнем в \(x\), так и с корнем в \(y\).

Вам дан неориентированный связный граф с \(n\) вершинами и \(m\) ребрами. Вычислите \(f(i,j)\) для всех \(i\), \(j\) по модулю \(998\,244\,353\).

Мышь нашла большой красивый торт и решила прогуляться по нему, попутно объедая ягоды на верхушке торта. Торт прямоугольный и разделен на аккуратные квадраты; в некоторых квадратах есть ягода, а в некоторых нет.

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

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

Вы бродите по исследовательской выставке на конференции 2050.

Выставка может быть представлена как неориентированный взвешенный граф в виде сетки размера \(n\times m\). Множество вершин графа это \(\{(i, j)|1\le i\le n, 1\le j\le m\}\). Две вершины \((i_1,j_1)\) и \((i_2, j_2)\) соединены ребром, если и только если \(|i_1-i_2|+|j_1-j_2|=1\).

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

Для каждой стартовой вершины \((i, j)\) найдите ответ на следующий вопрос: чему равна минимальная возможная скукота, если вы начнете в вершине \((i, j)\) и вернетесь обратно, сделав ровно \(k\) ходов.

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

В Шааззззляндии есть \(n\) городов, пронумерованных от \(0\) до \(n-1\). Гааззззляндией, бессмертным врагом Шааззззляндии, правит AaParsa.

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

AaParsa установил \(m\) транспортных пушек в городах Шааззззляндии. \(i\)-я пушка установлена в городе \(a_i\) и изначально направлена на город \(b_i\).

Гарантируется, что в каждом из \(n\) городов есть по крайней мере одна транспортная пушка, и что никакие две пушки из одного города изначально не направлены на один и тот же город (то есть, все пары \((a_i, b_i)\) попарно различны).

AaParsa использовал очень продвинутую технологию для создания пушек, пушки вращаются каждую секунду. Другими словами, если \(i\)-я пушка направлена на город \(x\) в какую-то секунду, то в следующую секунду она будет нацелена на город \((x + 1) \mod n\).

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

Если вы все еще не поняли, использование \(i\)-й пушки на \(s\)-й секунде (что возможно, только если вы в данный момент находитесь в городе \(a_i\)) запустит вас в город \((b_i + s) \mod n\), и вы приземлитесь в нем через \(c_i\) секунд (таким образом, вы окажетесь там в \((s + c_i)\)-ю секунду). Обратите внимание, что пушка, из которой вы изначально стартовали, будет вращаться каждую секунду, но вы, очевидно, не будете менять направление, пока находитесь в воздухе.

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

Обратите внимание, что AaParsa может оставаться в любом городе столько, сколько захочет.

Последний присоединившийся последователь Омкара, Ajit, вошел в Священный лес. Ajit понимает, что лес Омкара — это таблица размером \(n\) на \(m\) (\(1 \leq n, m \leq 2000\)), состоящая из целых неотрицательных чисел. Поскольку лес благословлен Омкаром, он удовлетворяет некоторым особым условиям:

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

К сожалению, Ajit еще не полностью достоин способностей Омкара. Он видит каждую клетку как "0" или "#". Если клетка обозначена как "0", то число в ней должно быть равно \(0\). Иначе число в ней может быть любым неотрицательным целым числом.

Определите, сколько существует различных конфигураций элементов, при которых выполняются эти особые условия. Две конфигурации считаются различными, если существует хотя бы одна клетка такая, что числа, записанные в ней в этих конфигурациях, различны. Поскольку ответ может быть огромным, найдите ответ по модулю \(10^9+7\).

На клетчатой полоске длины \(n\) расположены \(k\) кондиционеров: \(i\)-й кондиционер расположен в клетке \(a_i\) (\(1 \le a_i \le n\)). Два или более кондиционера не могут находиться в одной клетке (то есть все \(a_i\) различны).

Каждый кондиционер характеризуется еще одним параметром — температурой: \(i\)-й кондиционер включен на температуру \(t_i\).

Пример полосы длины \(n=6\), где \(k=2\), \(a=[2,5]\) и \(t=[14,16]\).

Для каждой клетки \(i\) (\(1 \le i \le n\)) найдите температуру воздуха в ней, которая равна \(\)\min_{1 \le j \le k}(t_j + |a_j - i|),\(\)

где \(|a_j - i|\) обозначает абсолютную величину (модуль) значения разности \(a_j - i\).

Иными словами, температура в клетке \(i\) равна минимуму среди температур кондиционеров, увеличенных на расстояние от кондиционера до клетки \(i\).

Рассмотрим пример. Пусть \(n=6, k=2\), первый кондиционер стоит в клетке \(a_1=2\) включен на температуру \(t_1=14\), а второй стоит в клетке \(a_2=5\) и включен на температуру \(t_2=16\). В таком случае температуры воздуха в клетках будут следующими:

1. температура в \(1\)-й клетке равна: \(\min(14 + |2 - 1|, 16 + |5 - 1|)=\min(14 + 1, 16 + 4)=\min(15, 20)=15\);
2. температура во \(2\)-й клетке равна: \(\min(14 + |2 - 2|, 16 + |5 - 2|)=\min(14 + 0, 16 + 3)=\min(14, 19)=14\);
3. температура в \(3\)-й клетке равна: \(\min(14 + |2 - 3|, 16 + |5 - 3|)=\min(14 + 1, 16 + 2)=\min(15, 18)=15\);
4. температура в \(4\)-й клетке равна: \(\min(14 + |2 - 4|, 16 + |5 - 4|)=\min(14 + 2, 16 + 1)=\min(16, 17)=16\);
5. температура в \(5\)-й клетке равна: \(\min(14 + |2 - 5|, 16 + |5 - 5|)=\min(14 + 3, 16 + 0)=\min(17, 16)=16\);
6. температура в \(6\)-й клетке равна: \(\min(14 + |2 - 6|, 16 + |5 - 6|)=\min(14 + 4, 16 + 1)=\min(18, 17)=17\).

Для каждой клетки от \(1\) до \(n\) найдите температуру воздуха в ней.

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

На текущем уровне герой попал в систему из \(n\) пещер, пронумерованных от \(1\) до \(n\), и \(m\) коридоров между ними. Каждый коридор соединяет две различные пещеры. Любые две пещеры соединены не более чем одним коридором. Из любой пещеры можно попасть в любую другую, двигаясь по коридорам.

Герой начинает уровень в пещере \(1\), а в каждой из оставшихся пещер находится монстр.

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

По любому коридору герой может перемещаться в обоих направлениях. Однако герой не может использовать один и тот же коридор два раза подряд. Формально, если герой перешёл по коридору из пещеры \(i\) в пещеру \(j\), он не может сразу же направиться обратно в пещеру \(i\), но может направиться в любую другую пещеру, соединённую коридором с пещерой \(j\).

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

Чтобы пройти уровень, герою нужно победить монстров во всех пещерах. Когда герой впервые зайдёт в пещеру, ему придётся драться с монстром в ней. Герой может победить монстра в пещере \(i\) только в том случае, если сила героя строго больше \(a_i\). В случае победы над монстром сила героя увеличится на \(b_i\). Если герой не может победить монстра, с которым он дерётся, игра заканчивается и игрок проигрывает.

После того, как герой победит монстра в пещере \(i\), все последующие визиты в пещеру \(i\) не будут иметь последствий — монстра в этой пещере уже не будет, но и сила героя не будет изменяться.

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

Let us consider the game "Sticky Tetris". In this game, there is a field of \(n \times m\) squares. Tiles appear on the field and the player can move the tiles.

Each tile is a \(4\)-connected set of at most \(7\) squares.

Each new tile appears in any position that fits inside the field, does not intersect any other tile, and the top cell of the tile is at the top row of the field. The player can move the tile left, right, and down, and at any moment the tile must still entirely fit inside the field and must not intersect other tiles. The player can stop the tile at any position at any time. After that, it cannot be moved. Since this is "Sticky Tetris," the tile will not fall once stopped.

You are given a final configuration of a "Sticky Tetris" game. You need to restore a sequence of steps that leads to that configuration if it exists.

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

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

Из-за технологических ограничений Нитори может строить только односторонние железные дороги. Их длина также может быть произвольным целым положительным числом. Строительство железной дороги в один конец от станции \(u\) будет стоить \(w_u\) единиц ресурсов независимо от станции назначения.

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

В силу разных причин стоимость строительства новой железной дороги иногда может расти бесконтрольно. Произойдут \(q\) событий, где \(i\)-е событие увеличивает стоимость постройки односторонних дорог из станции \(k_i\) на \(x_i\).

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

Лягушонок Горф отправился в путешествие по Болотному королевству. К несчастью, он не рассчитал длину своего прыжка и упал в колодец глубиной \(n\) метров. Теперь Горф лежит на самом дне колодца и ему предстоит долгий путь наверх.

Стенки колодца в некоторых местах скользкие, а в некоторых, наоборот, очень удобные. А именно, если Горф сейчас находится на глубине \(x\) метров от уровня земли, то за один прыжок он может подняться на любое расстояние от \(0\) по \(a_x\) метров вверх. (Заметим, что Горф не прыгает вниз, только вверх).

К сожалению, Горф не может прыгать без перерывов. После каждого прыжка ему нужно отдохнуть (даже после прыжка на \(0\) метров). А потому, после прыжка в позицию \(x\) метров ниже уровня земли, он соскользнет ровно на \(b_x\) метров вниз (пока отдыхает).

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

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

Влад построил лабиринт из \(n\) комнат и \(n-1\) двунаправленного коридора. Из любой комнаты \(u\) по коридорам достижима любая другая комната \(v\). Таким образом, система комнат образует неориентированное дерево.

Влад собрал \(k\) друзей, чтобы сыграть с ними в игру.

Влад начинает игру в комнате с номером \(1\) и выигрывает, если доходит до комнаты, отличной от \(1\), в которую ведёт ровно один коридор. Друзья же расставлены по лабиринту — друг с номером \(i\) стоит в комнате \(x_i\), и никакие два друга не стоят в одной комнате (то есть \(x_i \neq x_j\) для всех \(i \neq j\)). Друзья выигрывают, если одному удаётся встретиться с Владом в какой-либо комнате или коридоре, до того как он выиграет.

За одну единицу времени каждый участник игры может пройти по одному коридору. Все участники ходят одновременно. Участники также могут не двигаться. Каждая комната может вместить всех участников одновременно.

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

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