Кто-то предложил идею раздать каждому участнику по наклейке с логотипом BSUIR Open. Для этого в университете нашли прямоугольный лист самоклеящейся бумаги размером $$$n \times m$$$. Всего на соревнование приедут $$$k$$$ участников, поэтому необходимо вырезать ровно $$$k$$$ логотипов в форме квадрата одинакового размера. Теперь осталось определить максимальный размер каждой наклейки с логотипом.

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

Видимо наклейки будут уже в следующем году...

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

Среди всех видов связных неориентированных графов, Максим Витальевич подробно разобрался только в деревьях. Напомним, что дерево — это связный граф, не содержащий циклов, состоящий из $$$n$$$ вершин и $$$n - 1$$$ ребер. Другие виды графов вызывают некоторые трудности, так как в них могут быть циклы, либо они могут быть несвязными.

Чтобы разобраться с более сложными видами графов, Максим Витальевич решил их представлять в виде объединения набора деревьев. Для простоты он решил ограничиться только двумя деревьями. Для того, чтобы представить граф из $$$n$$$ вершин в виде объединения двух деревьев, Максим Витальевич раскрасил каждое ребро в один из трех цветов. Далее он построил первое дерево из $$$n$$$ вершин, используя ребра, раскрашенные цветами $$$1$$$ и $$$3$$$, а второе дерево из $$$n$$$ вершин — используя ребра, раскрашенные цветами $$$2$$$ и $$$3$$$. Таким образом, если объединить два дерева, то получится исходный граф, так как каждое ребро принадлежит как минимум одному дереву.

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

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

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

$$$$$$ \frac{1}{a} + \frac{1}{b} = \frac{c}{k} $$$$$$

Необходимо определить для заданного целого числа $$$k$$$ количество троек целых положительных чисел $$$a$$$, $$$b$$$ и $$$c$$$, являющихся решением данного уравнения, таких, что $$$a \le b$$$.

Максим Витальевич справился с решением данной задачи для заданного числа $$$k$$$ и теперь интересуется, а при каком $$$k$$$ ($$$1 \le k \le r$$$) количество решений будет максимальным.

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

• swap $$$x$$$ — поменять значения в вершине $$$x$$$ и родительской вершине $$$p$$$ местами.
• rotate $$$x$$$ — осуществить поворот (либо левый, либо правый) вершины $$$x$$$ и родительской вершины $$$p$$$.

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

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

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

После усердного поиска в интернете Максим Витальевич наткнулся на увлекательную игру-головоломку. В данной игре есть несколько уровней. На картинке ниже изображен пример уровня.

Каждый уровень представлен клетчатым полем размера $$$n \times m$$$, где $$$n$$$ – количество строк, а $$$m$$$ – количество столбцов. Каждая клетка этого поля либо свободна, либо занята препятствием, котом, котенком или собакой. На поле всегда находятся ровно один кот и один котенок, а также не более одной собаки. Игрок управляет передвижениями кота. Чтобы пройти уровень, игроку необходимо спасти котенка: за некоторое количество ходов переместить кота в клетку с котенком. За один ход игрок может переместить кота на соседнюю по горизонтали либо вертикали клетку, при этом он не может перемещать кота в клетку с препятствием. Если после хода кот оказался в клетке с котенком, то уровень считается пройденным. Если после хода кот оказался в клетке с собакой, то уровень считается непройденным (и его придется проходить заново).

После каждого хода игрока, при наличии собаки на поле, она осуществляет два хода. За один ход собака сближается с котом на одну клетку либо по вертикали, либо по горизонтали, при этом она не может перемещаться в клетку с препятствием. В качестве расстояния используется Манхэттенское расстояние между котом и собакой. Если собака может сблизиться и по горизонтали, и по вертикали, то она всегда сблизится по горизонтали (переместится либо влево, либо вправо). Если собака не может сблизиться, то она пропускает ход. Обратите внимание, что собака не может отдаляться от кота. Если собака после хода оказалась в клетке с котом, то уровень считается непройденным. Собака может перемещаться в клетку с котенком, при этом, если игрок переместится в клетку с котенком и собакой, то уровень также считается непройденным.

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

Максим Витальевич решил изучить новый язык программирования. Один его знакомый порекомендовал изучить язык Rust, так как он самый перспективный. Да, язык действительно воодушевляет, но заставляет столкнуться с суровой реальностью — великим и могучим borrow checker.

Сказать, что Максим Витальевич был в некоторой растерянности, это ничего не сказать. Чтобы выйти из данной ситуации и разобраться с borrow checker, Максим Витальевич решил упростить язык.

Новый язык поддерживает только заранее определенный набор функций. Всего в языке доступно $$$n$$$ функций, описание каждой имеет следующий синтаксис:

<char> := "a" | "b" | ... | "z"
<name> := <char> | <char> <name>
<nameOrRefName> := <name> | "&" <name>
<argument> := <nameOrRefName>
<arguments> := <argument> | <argument> ", " <arguments>
<functionName> := <nameOrRefName>
<functionArguments> := "" | <arguments>
<function> := "fn " <functionName> "(" <functionArguments> ")"

Таким образом, <function> является описанием функции. Можно заметить, что имя функции может быть как «name», так и «&name». В первом случае, функция возвращает значение, во втором случае — ссылку. Примеры корректных функций:

fn input()        // Функция input, возвращает значение и не содержит аргументов.
fn sum(a, b)      // Функция sum, возвращает значение и принимает два аргумента по значению.
fn add(&a, &b)    // Функция add, возвращает значение и принимает аргументы по ссылке.
fn &ref(a)        // Функция ref, возвращает ссылку и принимает аргумент по значению.
fn assign(a, &b)  // Функция assign, возвращает значение и принимает первый аргумент
                  // по значению, а второй по ссылке. 

Приведем также некорректные примеры (такие примеры не могут встречаться во входных данных):

&fn funcd()      // Неверный порядок символов.
fn funcb(a, b&)  // Неверный порядок символов.
fn funcc(&&a)    // Нельзя получить ссылку на ссылку.
fn &&funca()     // Нельзя вернуть ссылку на ссылку.
fn fn()          // Используется fn в качестве имени.
fn funce(fn)     // Используется fn в качестве имени.
fn funcf(a, a)   // Одинаковые имена аргументов.
fn funcg(a, &a)  // Одинаковые имена аргументов.

Чтобы реализовать некоторую программу, в языке доступна конструкция «<declare>» — объявление новой переменной (или ссылки). Можно описать синтаксис следующим образом:

<callArguments> := <expression> | <expression> ", " <callArguments>
<functionCallArguments> := "" | <callArguments>
<functionCall> := <name> "(" <functionCallArguments> ")"
<expression> := <nameOrRefName> | <functionCall>
<declare> := <name> " := " <expression>

Приведем корректные примеры использования конструкции:

a := input()      // Определяем переменную со значением результата input().
b := input()
c := a            // Приcваиваем новой переменной старое значение.
d := add(&b, &c)  // Вызываем функцию с передачей аргументов по ссылке.
e := add(ref(b), ref(c))
f := &e

Приведем некорректные примеры использования конструкции (такие примеры не могут встречаться во входных данных):

a := &input()  // Нельзя получить ссылку на результат функции.
fn := a        // Нельзя использовать fn в качестве имени.
&b := c        // Нельзя объявлять имя-ссылку.

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

Однако Максим Витальевич может допустить следующие ошибки:

• Использовать ранее не объявленную с помощью «:=» переменную.
• Использовать несуществующую функцию.
• Вызывать функцию с неверным числом аргументов (число аргументов должно совпадать с определением).
• В аргумент функции принимающий значение передавать ссылку (либо наоборот).
• Использовать в выражении ранее перемещенное значение переменной (либо ссылку на такую переменную).

Последний пункт рассмотрим поподробнее. В языке Максима Витальевича предусмотрен собственный механизм borrow checker. Суть заключается в том, что все переменные, которые используются по значению, перемещаются и перестают быть доступными. Рассмотрим следующий пример:

a := input()    // a является значением.
b := sum(a, a)  // Ошибка!

В этом случае переменная «a» передается по значению 2 раза, однако после первого же использования она перестает быть доступна, таким образом возникает ошибка. В то же время:

a := input()      // a является значением.
b := sum(&a, &a)  // Корректно, если sum принимает ссылки. Переменная a
                  // остается доступной, так как не была использована по значению.

После объявления переменной с тем же именем (:=), старая переменная (если она является значением) считается перемещенной и перестает быть доступной начиная со следующей строки.

Для ссылок действуют следующие правила:

• Нельзя получать ссылку для перемещенной переменной.
• Нельзя получать ссылку для переменной-ссылки.
• Нельзя использовать ссылку на перемещенную переменную.
• Нельзя одновременно передавать переменную-значение и ссылку на эту переменную в той же строке.

Рассмотрим следующие примеры:

a := input()
b := a
c := &a  // Ошибка, переменная a была перемещена.

a := input()
b := &a
c := move(a) // Аналогично c := a. В любом случае переменная a перемещается.
d := b       // Ошибка, переменная b является ссылкой на значение a, которое было перемещено.

a := input()
b := &a
c := call(a, b) // Ошибка. Переменная a была перемещена, поэтому ссылку использовать нельзя.

a := input()
b := &a
a := a         // Старое значение переменной a перемещено.
c := clone(b)  // Ошибка, переменная b ссылается на старую переменную a, которая
               // была перемещена в предыдущей строке.

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

Максима Витальевича пригласили на день рождения. Он выбрал, по его мнению, отличный подарок — торт в виде правильного выпуклого $$$n$$$-угольника.

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

Максим Витальевич задался вопросом, а за какое минимальное количество разрезаний можно разделить торт на треугольники. Разрешается разрезать торт только по диагоналям (прямым, проходящим через пару вершин $$$n$$$-угольника).

Вам дано дерево состоящее из $$$n$$$ вершин. В каждой вершине записан некоторый символ $$$c_i$$$. Вам необходимо удалить некоторое количество вершин так, чтобы оставшееся множество вершин было связным и при этом нельзя было найти палиндромного пути длиной более $$$k$$$. Простой путь называется палиндромным, если при выписывании символов, записанных в вершинах в прямом и обратном порядке, получается одна и та же строка.

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

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

Квантовую турбулентность можно описать следующим образом: турбулентность в измерении $$$i$$$ действует для координат $$$x_i \ge 1$$$. Если корабль находится в квантовой турбулентности для $$$i$$$-го измерения, то он становится неуправляемым в данном измерении. Вместо этого корабль перемещается из координаты $$$x_i$$$ в координату $$$x_i + 1$$$ с вероятностью $$$p$$$ и в координату $$$x_i - 1$$$ с вероятностью $$$q = 1 - p$$$. Если корабль попадает в координату $$$x_i \lt 1$$$, он снова становится управляемым и перестает случайно перемещаться в $$$i$$$-м измерении.

Вам необходимо определить вероятность $$$ans$$$, с которой Максим Витальевич сможет полностью восстановить управление по всем $$$n$$$ измерениям, если изначально он находится в координате $$$(a_1, a_2, ..., a_n)$$$.