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

Внимательно посмотрев на деталь и исправив формулу, Пин отметил, что сейчас в детали стоят две шестеренки с $$$a$$$ и $$$b$$$ зубцами соответственно, а работать правильно она будет с шестеренками размеров $$$a + x$$$ и $$$b + x$$$ соответственно, где $$$x$$$ — неотрицательное целое число такое, что $$$a + x$$$ делится на $$$b$$$, и $$$b + x$$$ делится на $$$a$$$.

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

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

Лабиринт состоит из $$$n$$$ комнат, пронумерованных от $$$1$$$ до $$$n$$$, некоторые из которых соединены между собой коридорами. Известно, что между любыми двумя комнатами существует единственный путь из коридоров. Иными словами, лабиринт представляет собой дерево, и количество коридоров равно $$$n - 1$$$.

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

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

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

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

Изначально все Смешарики находятся в узлах целочисленной сетки. Если Смешарик находится в точке $$$(x, y)$$$, то за одну секунду он может переместиться в точки $$$(x, y + 1)$$$, $$$(x + 1, y)$$$, $$$(x - 1, y)$$$ или $$$(x, y - 1)$$$, или же остаться в точке $$$(x, y)$$$.

У Совуньи была цепочка, состоявшая из $$$n$$$ звеньев, пронумерованных от $$$1$$$ до $$$n$$$. Но пока цепочка валялась в комоде, она вся запуталась. Совунья хочет исправить ситуацию.

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

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

В конце все звенья должны быть запаянными.

Совунья хочет, чтобы звено номер $$$1$$$ было сцепленно со звеном номер $$$2$$$, $$$2$$$ с $$$3$$$, ..., $$$n - 1$$$ с $$$n$$$. Иными словами, чтобы были сцеплены звенья с номерами $$$i$$$ и $$$i + 1$$$ для всех $$$i \in [1, n - 1]$$$. А никакие другие пары звеньев не должны быть сцеплены.

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

Роясь в одном из сундуков у себя дома, Карыч нашел старый кнопочный телефон. На этом телефоне есть всего одна игра, зато какая! Змейка! Раньше Карыч много играл в нее, пока, например, ехал в поезде или стоял в очереди.

Игра происходит на клетчатом поле $$$n \times m$$$. Поле не является зацикленным ни по вертикали, ни по горизонтали. То есть, если змейка врежется в границу поля, игра закончится проигрышем. Строки поля пронумерованы от $$$1$$$ до $$$n$$$ сверху вниз, а столбцы — от $$$1$$$ до $$$m$$$ слева направо.

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

На каждом ходу игрок должен выбрать одно из четырех направлений движения: «вверх», «вниз», «влево» или «вправо». После этого, игра находит соседнюю с головой змейки клетку в выбранном игроком направлении. Назовем её $$$q$$$.

• Если в выбранном направлении нет клетки, то есть игрок сходил за границу поля, игра заканчивается.
• Иначе, если в $$$q$$$ находится яблоко, змейка его съедает, её длина увеличивается на $$$1$$$, и клетка $$$q$$$ добавляется в начало последовательности клеток, представляющих змейку.
• Иначе, сначала из последовательности клеток удаляется последняя (хвост). Затем, если клетка $$$q$$$ все еще встречается в последовательности, значит змейка врезалась сама в себя, поэтому игра заканчивается. Иначе, клетка $$$q$$$ дописывается в начало последовательности.

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

В начале игры змейка имеет длину $$$1$$$.

Карыч слышал, что если выиграть в этой игре, то есть заполнить змейкой все клетки поля, то игра покажет мультик. Но ему никогда не удавалось этого достичь. Помогите ему! Вы должны сделать не более $$$100\,000$$$ ходов.

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

Во второй строке даны два целых числа $$$x_s$$$ и $$$y_s$$$ — номер строки и столбца, на пересечении которых находится клетка, из которой состоит змейка в начале игры ($$$1 \le x_s \le n$$$, $$$1 \le y_s \le m$$$).

В третьей строке даны два целых числа $$$x_a$$$ и $$$y_a$$$ — координаты клетки, в которой в начале игры находится яблоко ($$$1 \le x_a \le n$$$, $$$1 \le y_a \le m$$$).

Далее, вы должны взаимодействовать в тестирующей программой. На каждом ходу вы должны вывести один из символов, обозначающих направление движения: «U» (вверх), «D» (вниз), «L» (влево) или «R» (вправо).

Затем, программа выведет один из нескольких возможных ответов:

• «fail» — означает, что змейка врезалась в стену, съела себя, или у вас закончились ходы, но вы не выиграли. В этом случае, вы должны немедленно завершить исполнение программы, чтобы получить вердикт WA. Иначе, вы можете получить произвольный вердикт (отличный от AC).
• «win» — длина змейки стала равна $$$n \cdot m$$$, вы выиграли. Нужно, не выводя больше ничего, завершить исполнение программы.
• «ok» — вы сделали корректный ход. В результате хода, голова змейки сдвинулась в выбранном вами направлении, длина змейки не изменилась.
• «new» — вы сделали корректный ход и змейка съела яблоко. Голова змейки сдвинулась в выбранном направлении, длина змейки увеличилась на $$$1$$$. В следующей строке даны два целых числа $$$x_a$$$ и $$$y_a$$$ — координаты новой позиции яблока ($$$1 \le x_a \le n$$$, $$$1 \le y_a \le m$$$).

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

Не забывайте после каждого вывода переводить строку и сбрасывать буфер вывода. Подробнее можно прочитать в блоге на codeforces: https://codeforces.me/blog/entry/45307.

После того, как Копатыч своей тачкой въехал в очередной механизм Пина, тот рассердился и на собрании Смешариков установил новый порядок пользования землёй. Теперь каждый Смешарик, который хочет использовать какой-то участок страны Смешариков, должен его задекларировать в специальной книжечке, хранящейся у Ёжика. Страну Смешариков можно представить в виде клетчатого прямоугольника с вертикальной стороной $$$H$$$ и горизонтальной стороной $$$W$$$.

На следующий день ровно в 8:01 к двери Ёжика одновременно примчались Совунья и Нюша: Совунья хотела выделить место под спортивную площадку, а Нюше нужна была зона для упражнений по кордебалету.

Чтобы предотвратить споры, Ёжик сказал Нюше и Совунье, чтобы они заранее договорились, кому какой участок нужен, и только потом шли записываться в книжечку. Также он установил некоторые правила:

• Оба участка должны являться непустыми подпрямоугольниками страны Смешариков.
• Высота каждого из прямоугольников не может превышать $$$h$$$, а ширина — $$$w$$$.
• Прямоугольники не должны иметь общих клеток (но могут касаться).

Теперь Совунья и Нюша стоят дома у Ёжика перед картой и перебирают все варианты, как они могли бы выбрать два прямоугольника. Помогите Ёжику оценить, на сколько затянется это нарушение личных границ, и найдите число способов выбрать два прямоугольника, удовлетворяющих указанным ограничениям. Это число может быть достаточно велико, так что вычислите его по модулю $$$10^9 + 7$$$.

Сегодня Крош узнал про среднее геометрическое чисел. Среднее геометрическое двух положительных чисел $$$x$$$ и $$$y$$$ равно $$$\sqrt{x \cdot y}$$$. Обозначим среднее геометрическое чисел $$$x$$$ и $$$y$$$ как $$$g(x, y)$$$.

У Кроша было три положительных вещественных числа $$$a$$$, $$$b$$$ и $$$c$$$. Он использовал их, чтобы попрактиковаться в вычислении средних геометрических. Он вычислил и записал числа $$$g(a, b)$$$, $$$g(a, c)$$$ и $$$g(b, c)$$$.

Спустя некоторое время, Крош увидел записанные значения средних геометрических. И теперь он хочет вспомнить, какие числа $$$a$$$, $$$b$$$ и $$$c$$$ у него были. Помогите ему найти любые подходящие положительные числа $$$a$$$, $$$b$$$ и $$$c$$$.

Лосяш решил сделать обучение более доступным для Смешариков и открыл школу. Разумеется, как и в любой другой школе, в этой школе есть учителя (например, Пин и Совунья) и есть ученики (например, Крош и Ёжик). Ну и, конечно же, Лосяш — директор. Всего суммарно в школе $$$n$$$ Смешариков (преподавательского состава и учеников). Для удобства, пронумеруем их натуральными числами от $$$1$$$ до $$$n$$$.

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

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

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

Лосяш хочет оптимизировать учебный процесс, поэтому в некоторые моменты времени ему интересно, сколько непрочитанных сообщений есть у какого-то конкретного пользователя.

Вам дана последовательность из $$$q$$$ событий в том порядке, в котором они происходили. Для каждого события, соответствующего вопросу Лосяша, выведите ответ.

Лосяш решил заняться бегом и для этой цели взял у Пина секундомер. Через несколько недель Лосяш стал поспортивнее и стал делать за раз больше одного круга на стадионе. Тут-то он и столкнулся с классической проблемой лёгкой атлетики: если достаточно долго бежишь, то забываешь, сколько кругов ты уже пробежал и сколько тебе осталось. К счастью, на секундомере был специальный индикатор, который показывает текущий номер круга. Теперь каждый раз, пробегая через финишную черту, Лосяш нажимал специальную кнопку на секундомере, и число на индикаторе возрастало на единицу.

Что же это за индикатор такой, спросите вы, который может отображать сколь угодно большие натуральные числа? А он и не может. В основе индикатора лежит шестерёнка с $$$m$$$ зубьями, на которых написаны натуральные числа от 1 до $$$m$$$, вращающаяся при нажатии кнопки. Таким образом, если число, отображаемое индикатором, дошло до $$$m$$$, и Лосяш нажал кнопку, то оно сбрасывается до единицы.

Один раз после пробежки Лосяш вспомнил, что Совунья просила его одолжить секундомер, чтобы она могла в точности по рецепту приготовить сычуаньский соус. Лосяш просто обожает этот соус, поэтому он тут же пошёл к Совунье и решил, кроме того, сделать ей приятно и выставить на индикаторе $$$b$$$ — любимое число Совуньи (так удачно совпало, что это было как раз число от 1 до $$$m$$$, то есть индикатор был способен его отобразить). В тот момент на индикаторе отображалось число $$$a$$$.

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

Бараш увлекся бегом. А чтобы не было скучно, во время бега он слушает музыку.

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

Всего за время пробежки он целиком послушал $$$n$$$ песен. Для каждой песни он выписал ее длительность в формате mm:ss. До двоеточия стоят ровно две цифры, обозначающие количество минут, а после — ровно две цифры, обозначающие количество секунд. Каждая песня длится строго меньше часа, количество минут и секунд лежат в отрезке от $$$0$$$ до $$$59$$$ включительно.

Помогите Барашу определить длительность пробежки и выведите ее в формате hh:mm:ss. Сначала ровно две цифры, обозначающие количество часов, затем две цифры — количество минут, и наконец — количество секунд. Гарантируется, что Бараш бегал строго меньше суток. Количество часов должно лежать в отрезке от $$$0$$$ до $$$23$$$, а количество минут и секунд — в отрезке от $$$0$$$ до $$$59$$$.