Конструктив

На производстве расположены \(n\) роботов, пронумерованных от \(1\) до \(n\). Любая пара роботов может быть либо соединена проводом, либо нет. Известно, что \(i\)-й робот соединен с \(k_i\) другими роботами с номерами \(v_{i,1}, \ldots, v_{i,k_i}\). Провода двухсторонние, то есть если \(i\) связан с \(j\), то \(j\) связан с \(i\) (иными словами, \((i, j)\) и \((j, i)\) — это один и тот же провод).

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

• либо если \(t = n\);

• либо если существуют такие \(i_1, \ldots, i_k\), что \(i_1 = n\), \(i_k = t\), и любые два соседних в этой последовательности робота \(i_j\) и \(i_{j + 1}\) связаны проводом.

Любому из роботов, которыми можно управлять, можно послать команду <<извлеки второй конец подключенного к себе провода и подключи его к другому роботу>>. Иными словами, если роботом номер \(t\) можно управлять, и есть провод, соединяющий его с роботом номер \(x\), то можно заменить провод \((t, x)\) на провод \((t, y)\) для любого \(y \neq t\), еще не связанного проводом с \(t\). Обратите внимание, что после этого вы можете потерять управление над \(t\)-м роботом, если единственная связь \(t\)-го с \(n\)-м проходила через \(x\)-й.

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

Формат входных данных
В первой строке записано целое число \(T\) (\(1 \le T \le 1000\)) — количество наборов входных данных в тесте.

Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(1 \leq n \leq 10^5\)) — количество роботов.

Затем следуют \(n\) строк, в \(i\)-й из которых записаны числа \(k_i\) (\(0 \le k_i \le n - 1\)) и \(v_{i,1}, \ldots, v_{i,k_i}\) (\(1 \le v_{i,j} \le n\); \(v_{i,j} \neq i\)) — количество проводов, подключенных к \(i\)-му роботу, и номера роботов на противоположных концах этих проводов. Гарантируется, что данные корректны: никакие два провода не соединяют одну и ту же пару роботов, и если \(j \in v_i\), то \(i \in v_j\).

Также гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\) и сумма количества проводов по всем наборам входных данных не превосходит \(1.5 \cdot 10^5\).

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

В следующих \(k\) строках выведите сами описания действий в формате <<\(y\) + \(t\) - \(x\)>> (\(1 \leq t, x, y \leq n\); \(x \neq y\)). Каждая такая строка соответствует замене провода \((t, x)\) на провод \((t, y)\).

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

На производстве расположены \(n\) роботов, пронумерованных от \(1\) до \(n\). Любая пара роботов может быть либо соединена проводом, либо нет. Всего на производстве \(m\) проводов и \(i\)-й из них сейчас соединяет роботов с номерами \(a_i\) и \(b_i\).

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

• либо если \(t = 1\);

• либо если существуют такие \(i_1, \ldots, i_k\), что \(i_1 = 1\), \(i_k = t\), и любые два соседних в этой последовательности робота \(i_j\) и \(i_{j + 1}\) связаны проводом.

Любому из роботов, которыми можно управлять, можно послать команду <<извлеки второй конец подключенного к себе провода и подключи его к другому роботу>>. Иными словами, если роботом номер \(t\) можно управлять, и есть провод, соединяющий его с роботом номер \(x\), то можно заменить провод \((t, x)\) на провод \((t, y)\) для любого \(y \neq t\), еще не связанного проводом с \(t\). Обратите внимание, что после этого вы можете потерять управление над \(t\)-м роботом, если единственная связь \(t\)-го с первым проходила через \(x\)-й.

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

Формат входных данных
В первой строке записано целое число \(T\) (\(1 \le T \le 1000\)) — количество наборов входных данных в тесте.

Первая строка каждого набора входных данных содержит целые числа \(n\) и \(m\) (\(1 \leq n \leq 10^5\); \(0 \leq m \leq 1.5 \cdot 10^5\)) — количество роботов и количество проводов, соответственно.

В следующих \(m\) строках дано описание проводов: в \(i\)-й строке даны целые числа \(a_i\) и \(b_i\) (\(1 \leq a_i, b_i \leq n\); \(a_i \neq b_i\)) — номера роботов, соединенных \(i\)-м проводом. Гарантируется, что никакие два провода не соединяют одну и ту же пару роботов.

Также гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\) и сумма \(m\) по всем наборам входных данных не превосходит \(1.5 \cdot 10^5\).

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

В следующих \(k\) строках выведите сами описания действий по одному на каждой строке. Описание действия должно состоять из трех целых чисел \(t\), \(x\) и \(y\) (\(1 \leq t, x, y \leq n\); \(x \neq y\)), означающих, что робот номер \(t\) меняет провод \((t, x)\) на провод \((t, y)\).

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

Как вы знаете, девочка Даша постоянно что-то ищет. На этот раз ей дали перестановку, и она хочет найти такой её подотрезок, что ни один из элементов на его концах не является ни минимумом, ни максимумом всего подотрезка. Более формально, вас просят найти такие числа \(l\) и \(r\) \((1 \leqslant l \leqslant r \leqslant n)\), что \(a_l \neq \min(a_l, a_{l + 1}, \ldots, a_r)\), \(a_l \neq \max(a_l, a_{l + 1}, \ldots, a_r)\) и \(a_r \neq \min(a_l, a_{l + 1}, \ldots, a_r)\), \(a_r \neq \max(a_l, a_{l + 1}, \ldots, a_r)\).

Напомнима, что перестановкой длины \(n\) называется массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\), выписанных в произвольном порядке. Например, \([2,3,1,5,4]\) является перестановкой, но \([1,2,2]\) не является перестановкой (\(2\) встречается дважды в массиве) и \([1,3,4]\) тоже не является перестановкой (\(n=3\), но \(4\) присутствует в массиве, а \(2\) отсутствует).

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

Формат входных данных
В первой строке входных данных вам дано одно целое число \(n\) (\(1 \leqslant n \leqslant 200\,000\)) — размер перестановки.

Во второй строке входных данных вам дано \(n\) целых чисел \(a_1, a_2, \ldots a_n\) (\(1 \leqslant a_i \leqslant n\)) — элементы перестановки.

Формат выходных данных
Если искомого подотрезка не существует, выведите \(-1\).

Иначе выведите такие два числа \(l\) и \(r\) \((1 \leqslant l \leqslant r \leqslant n)\), что \([a_l, a_{l + 1}, \ldots, a_r]\) удовлетворяет условиям задачи.

Если искомых подотрезков несколько, выведите любой из них.

Недавно Феде на день рождения подарили массив из \(n\) целых чисел, записаных по кругу, в котором для каждой пары соседних элементов (\(a_1\) и \(a_2\), \(a_2\) и \(a_3\), \(\ldots\), \(a_{n - 1}\) и \(a_n\), \(a_n\) и \(a_1\)) модуль их разности равен \(1\) (два соседних элемента отличаются ровно на \(1\)).

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

К сожалению, Федя потерял массив, но он запомнил в нём сумму локальных максимумов \(A\) и сумму локальных минимумов \(B\).

По заданным \(A\) и \(B\) помогите найти любой из подходящих массивов.

Формат входных данных
В первой строке вводится целое число \(A\) (\(-10^{18} \leqslant A \leqslant 10^{18}\)).

Во второй строке вводится целое число \(B\) (\(-10^{18} \leqslant B \leqslant 10^{18}\), \(B < A\)).

В третьей строке вводится целое число \(t\) (\(0 \leqslant t \leqslant 1\)) — если \(t = 0\), то от вас требуется вывести только длину массива.

Гарантируется, что при \(t = 1\) выполняется \(A - B \leqslant 10^{5}\).

Обратите внимание, что входные данные могут быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.

Формат выходных данных
В первой строке выведите одно число \(n\) — длину массива. При \(t = 0\) должно быть верно, что найдется хотя бы один подходящий массив с такой длиной.

Если \(t = 1\), то выведите во второй строке \(n\) чисел \(a_1, a_2, \ldots, a_n\) (\(-10^{18} \leqslant a_i \leqslant 10^{18}\)) — элементы массива.

Гарантируется, что при \(t = 1\) существует массив, размер которого не превосходит \(4 \cdot 10^5\).

Если \(t = 0\), то во второй строке выводить ничего не нужно.

В первом примере локальными максимумами являются числа на позициях \(3\) и \(10\), а локальными минимумами числа на позициях \(6\) и \(8\).

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

Все квесты в игре имеют одинаковую структуру. Пусть на карте расположены \(m\) комнат. Тогда каждый квест задаётся парой комнат \(u\) и \(v\) (\(1 \le u \le v \le m\)). Для прохождения этого квеста игроку нужно переместиться из комнаты \(u\) в комнату \(v\). Для усложнения игры в каждой комнате, через которую пройдёт игрок (включая начальную и конечную комнату) необходимо решить загадку. Влад называет сложностью квеста минимальное количество загадок, которые надо решить, чтобы его пройти. В частности, сложность квеста, у которого начальная и конечная комната совпадает, равна \(1\), а сложность квеста, в котором начальная и конечная комнаты соединены коридором равна \(2\). Также Влад называет квест трудным, если не существует квеста с большей сложностью, чем данный.

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

Формат входных данных
В первой строке задано целое число \(n\) (\(1 \le n \le 500\)) — требуемое количество трудных уровней.

Формат выходных данных
В первой строке выведите целое число \(m\) — минимальное количество комнат на карте.

В следующих \(m - 1\) строках выведите через пробел пары целых чисел \(u\) и \(v\), обозначающие коридор, между комнатами \(u\) и \(v\).

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

Примечание
В первом примере карта выглядит так:

На этой карте есть 10 квестов. Обозначим за (u, v) квест, который начинается в комнате с номером u и заканчивается в комнате с номером v. Сложность квестов (1, 1), (2, 2), (3, 3) и (4, 4) равна 1, сложность квестов (1, 2), (1, 3) и (1, 4) равна 2, а сложность квестов (2, 3), (2, 4) и (3, 4) равна 3. Таким образом, трудными квестами являются квесты (2, 3), (2, 4) и (3, 4). Трудных квестов 3, значит интересность игры на данной карте равна 3.

Во втором тестовом примере карта выглядит так:

На этой карте есть 4 трудных квеста (2, 5), (2, 6), (3, 5) и (3, 6). Их сложность равна 4.

В третьем тестовом примере карта выглядит так:

На этой карте есть 5 трудных квестов (2, 8), (3, 8), (4, 8), (5, 8), (6, 8) со сложностью 4.

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

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

Головоломка представляет из себя таблицу из \(n\) строк и \(m\) столбцов, в ячейках которой записаны числа от \(1\) до \(n \cdot m\) по одному разу.

Чтобы собрать головоломку, нужно выбрать последовательность клеток таблицы, в которой любые две подряд идущие клетки соседние по стороне в таблице. Последовательность может иметь произвольную длину, и каждая клетка может встречаться в последовательности произвольное число раз. Для клетки со значением \(i\) рассмотрим позицию \(t_i\) — позицию первого вхождения клетки с таким значением в последовательность. Последовательность решит головоломку, если каждая клетка таблицы встречается в ней, и \(t_1 < t_2 < \dots < t_{nm}\). Другими словами, последовательность должна в первый раз посетить клетку со значением \(x\) до клетки со значением \(x + 1\) для всех \(x\).

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

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

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

Формат входных данных
В первой строке вводятся два целых положительных числа \(n, m\) (\(1 \leq n \cdot m \leq 400\,000\)) — длины сторон таблицы.

В каждой из следующих \(n\) строках вводятся \(m\) целых чисел \(a_{i1}, a_{i2}, \dots, a_{im}\) (\(1 \le a_{ij} \le n \cdot m\)).

Гарантируется, что каждое число от \(1\) до \(n \cdot m\) встречается ровно один раз.

Формат выходных данных
Пусть \(a\) — минимальное число действий, после которых головоломка станет решаемой.

Если \(a = 0\), выведите \(0\).

Если \(a = 1\), выведите \(1\), а также количество подходящих пар клеток.

Если \(a \ge 2\), выведите \(2\).

В первом примере из условия последовательность клеток \((1, 2), (1, 1), (1, 2), (1, 3), (2, 3), (3, 3)\), \((2, 3), (1, 3), (1, 2), (1, 1), (2, 1), (2, 2), (3, 2), (3, 1)\) решает головоломку, поэтому ответ \(0\).

Головоломка во втором примере из условия не решается, но будет решаться после любого из трех обменов клеток со значениями \((1, 5), (1, 6), (2, 6)\).

В третьем примере из условия потребуется не менее двух обменов, поэтому ответ равен \(2\).

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

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

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

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

Формат входных данных
Первая строка входных данных содержит целое число n (1 ≤ n ≤ 10⁶) - количество задач в олимпиаде.
Вторая строка входных данных содержит целое число n (1 ≤ x_i ≤ 3) - количество страниц в i-й задаче.
Формат выходных данных
Выведите единственное число - минимальное количество последовательных диапазонов, каждый из которых можно напечатать одной командой односторонней или двусторонней печати так, что условия всех задач будут напечатаны в удобном для командной олимпиады виде.

Замечание
В первом примере на олимпиаду предложены 4 задачи, условия которых состоят из 1, 3, 2 и 1 страниц соответственно. Всего необходимо распечатать 7 страниц. Их можно распечатать за два задания: cтраницы 1-2 - односторонней печатью (это единственная страница первой задачи и первая из трёх страниц второй задачи), оставшиеся страницы 3-7 - двусторонней.

Во втором примере на олимпиаду предложены 2 задачи, условия которых состоят из 3 страниц каждая. Всего необходимо распечатать 6 страниц. Их можно распечатать за два задания: cтраницы 1-1- односторонней печатью (это первая из трёх страниц первой задачи), оставшиеся страницы 2-6 - двусторонней. При этом в первой задаче первая страница будет напечатана на одной стороне,  потому что она напечатана односторонней печатью, а во второй задаче последняя страница будет напечатана на одной стороне, потому что в этом задании нечётное число страниц печатается на двух сторонах, поэтому вторая сторона этого листа будет пустой.

Саша Белый и его бригада приехали на переговоры в Сатку. Однако беседа обещает быть жаркой, поэтому Саша хочет спрятать свою братву в засаду. Переговоры будут проходить на квадратном поле размером 2N×2N, и в каждую клетку этого поля Белый может посадить от 0 до 2 братанов. Так как Саша не любит повторяться, то суммарное количество братанов в каждом столбце и в каждой строке квадратного поля должно быть различным.
Как вы знаете, из-за определённых обстоятельств Белый не закончил вуз, поэтому не силён в программировании, и вам нужно срочно помочь ему.
Подскажите Белому, сможет ли он расставить братву с заданным условием, и если сможет, то приведите пример расстановки.
Входные данные
Во входных данных записано единственное целое число N такое, что 2N — длина стороны поля (1 <= N <= 300).
Выходные данные
На первой строке выведите YES, если существует расстановка, что суммарное количество братанов в каждом столбце и в каждой строке квадратного поля различно, и NO в противном случае. Если расстановка существует, то на следующих 2N строках выведите пример. Если существует несколько подходящих расстановок, то можете вывести любую из них.
 

Примеры

№	Входные данные	Выходные данные
1	1	YES 0 0 1 2
2	2	YES 0 1 0 2 2 2 0 2 0 2 1 2 0 2 0 2

Ушан решил сыграть в карточную игру. У него есть колода, состоящая из N съедобных карт. На i-й карте сверху написано целое число Ai. Ушан выполняет описанную ниже операцию ноль или более раз, так что значения, записанные на оставшихся карточках, будут попарно различны.
Найдите максимально возможное количество оставшихся карт. Здесь N нечетное, что гарантирует сохранение хотя бы одной карты. 
Операция: вынуть из колоды три произвольные карты. Из этих трех карт съешьте две: одну с наибольшим значением, а другую с наименьшим значением. Затем верните оставшуюся одну карту в колоду.

Входные данные
В первой строке записано нечетное число N (\(3<=N<=10^5\)). Во второй строке записаны N чисел Ai (\(1<=A_i<=10^5\))

Выходные данные
Выведите максимально возможное количество оставшихся карт.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	5 1 2 1 3 7	3	Оптимальное решение - выполнить операцию один раз, вынув две карты с 1 и одну карту с 2. Одна карта с 1 и другая с 2 будут съедены, а оставшаяся карта с 1 будет возвращена в колоду. Тогда значения, написанные на оставшихся картах в колоде, будут попарно различными: 1, 3 и 7.
2	15 1 3 5 2 1 3 2 8 8 6 2 6 11 1 1	7

 

Назовём палиндромом непустую строку, которая читается одинаково справа налево и слева направо. Например, « abcba », « a » и « abba » являются палиндромами, а « abab » и « xy » не являются.

Назовём подстрокой строки строку, полученную отбрасыванием некоторого (возможно, нулевого) количества символов с начала и с конца строки. Например, « abc », « ab » и « c » являются подстроками строки « abc », а « ac » и « d » не являются.

Назовем палиндромностью строки количество её подстрок, которые являются палиндромами. Например, палиндромность строки « aaa » равна 6, так как все её подстроки являются палиндромами, а палиндромность строки « abc » равна 3, так как только подстроки длины 1 являются палиндромами.

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

Входные данные
В первой строке задано целое число n (1 ≤ n ≤ 100000) — длина строки s.

Во второй строке задана строка s, состоящая из n строчных букв латинского алфавита.

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

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

Примечание
В первом примере у строки « ololo » есть 9 подстрок-палиндромов: « o », « l », « o », « l », « o », « olo », « lol », « olo », « ololo ». Обратите внимание, что некоторые подстроки совпадают, но учитываются несколько раз.

Во втором примере палиндромность строки « abccbaghghghgdfd » равна 29.
 

Примеры

№	Входные данные	Выходные данные
1	5 oolol	ololo
2	16 gagadbcgghhchbdf	abccbaghghghgdfd

Новый квест, в котором участники должны выбраться с территории проведения, представляет собой прямоугольник из N × M комнат. Каждая комната имеет четыре двери, ведущие в соседние комнаты, из комнат на краю прямоугольника двери ведут наружу, через эти двери можно
покинуть территорию проведения квеста.
В начале квеста в каждой комнате находится по человеку, а все двери заперты. После начала квеста организаторы дистанционно открывают в каждой комнате запирающий механизм одной из четырёх дверей. Теперь человек, находящийся в этой комнате, может открыть эту дверь и перейти
в соседнюю комнату, через другие три двери выйти из этой комнаты нельзя. При этом может оказаться так, что дверь, соединяющая две комнаты, будет отпираться только с одной стороны, тогда пройти через эту дверь можно только с той стороны, с которой она будет открываться, проходить
через дверь в обратном направлении нельзя, если в соседней комнате будет отперта не эта дверь, а какая-то другая. Если комната находится на краю территории и из этой комнаты открыта дверь наружу, то, пройдя через эту дверь, участник навсегда покидает территорию квеста.
После начала квеста и отпирания дверей участники начинают перемещаться между комнатами. Каждый участник перемещается в соседнюю открытую комнату и продолжает перемещаться до тех пор, пока не покинет территорию квеста. Однако возможна ситуация, когда некоторые участники будут бесконечно перемещаться между комнатами и никогда не выйдут наружу.
Разработчики квеста попросили Вас составить такой план отпирания дверей, при котором ровно K человек смогут выбраться наружу с территории квеста.
Входные данные
Программа получает на вход три числа N, M, K, 1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 0 ≤ K ≤ NM. N и M – количество строк и столбцов в прямоугольном плане квеста, K – количество человек, которые должны выйти из квеста.
Выходные данные
Программа должна вывести план территории квеста в виде N строк, каждая из которых должна содержать M символов. Символ соответствует тому, какая дверь будет открыта в данной комнате и может быть одной из следующих заглавных английских букв: U (дверь в верхнюю по данному плану комнату), D (дверь в нижнюю комнату), L (дверь в левую комнату), R (дверь в правую комнату). Необходимо вывести один любой подходящий план решения задачи. Если ни одного подходящего плана не существует, программа должна вывести одну строчку «IMPOSSIBLE».».
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	1 2 1	IMPOSSIBLE	Территория квеста состоит из 1 строки и 2 столбцов. При любом способе открытия дверей из квеста не сможет выбраться ровно один человек.
2	3 4 5	RDLD ULUR DURU	Территория квеста состоит из 3 строк и 4 столбцов. Из квеста должны выйти 5 человек. На рисунке ниже приведена картинка, соответствующая ответу из примера. Стрелками обозначены открытые двери, точками помечены комнаты, обитатели которых выйдут из квеста.

Даны три строки, состоящие из строчных латинских букв. С этими строками можно производить следующие операции: либо заменить один символ строки на два таких же символа (например, заменить символ «a» на «aa»), либо, наоборот, заменить два подряд идущих одинаковых символа на один такой же символ.

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

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

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

Примеры

№	Входные данные	Выходные данные
1	aaaza aazzaa azzza	aazza
2	xy xxyy yx	IMPOSSIBLE

В 2037-м году для создания научно исследовательской базы на Марс высадился отряд роботов, один из которых отправился собирать информацию о районе дислокации. В данный момент роботу из-за отказа некоторых узлов срочно необходимо вернуться в место закладки будущей базы.
Поверхность Марса в районе высадки десанта можно условно представить в виде плоскости с введенной на ней системой координат, такой, что база находится в точке (0, 0). Робот же остановился в точке (x₀, y₀). Он может перемещаться в четырёх направлениях:
• «R» — вправо, при этом координата x робота увеличивается на 1;
• «L» — влево, при этом координата x робота уменьшается на 1;
• «U» — вверх, при этом координата y робота увеличивается на 1;
• «D» — вниз, при этом координата y робота уменьшается на 1.
Из-за неисправности робот не может совершить два перемещения подряд в одном направлении.
Помогите роботу вернуться на базу. Робот должен сделать не более 10000 передвижений, иначе он разрядится и не доедет до базы!

Входные данные
В единственной строке входных данных находятся два целых числа x0 и y0 — изначальные координаты робота (−1000 ≤ x0, y0 ≤ 1000).

Выходные данные
В первой строке выведите целое число, не большее 10000 — количество операций, которые должен сделать робот. Во второй строке выведите сами операции. Каждая операция задаётся одной буквой:
вправо — «R» влево — «L», вверх — «U», вниз — «D». Символы необходимо выводить без пробелов между ними.
 

Примеры

№	Входные данные	Выходные данные
1	2 1	5 DLULD

Замечание
Вы не обязаны выводить кратчайший маршрут. Например, в приведенном примере кратчайший
маршрут состоит из 3 передвижений: влево, вниз, влево.
Иллюстрация к тесту из примера:

Boolean satisfiability problem (SAT) is known to be a very hard problem in computer science. In this problem you are given a Boolean formula, and you need to find out if the variables of a given formula can be consistently replaced by the values true or false in such a way that the formula evaluates to true. SAT is known to be NP-complete problem. Moreover, it is NP-complete even in case of 3-CNF formula (3-SAT). However, for example, SAT problem for 2-CNF formulae (2-SAT) is in P.

#SAT is the extension of SAT problem. In this problem you need to check if it is possible, and count the number of ways to assign values to variables. This problem is known to be #P-complete even for 2-CNF formulae. We ask you to solve #1-DNF-SAT, which is #SAT problem for 1-DNF formulae.
You are given a Boolean formula in 1-DNF form. It means that it is a disjunction (logical or) of one or more clauses, each clause is exactly one literal, each literal is either variable or its negation (logical not). Formally:

На занятиях по дискретной математике Сереже рассказали про двоичные коды Грея — это такое упорядочение всех 2ⁿ различных двоичных векторов длины n, что любые два соседних, а также первый и последний, вектора различаются ровно в одном разряде.

Для закрепления материала преподаватель задал им следующее задание: в коде Грея в каждом двоичном векторе ровно один бит заменен на знак вопроса «?». Требуется заменить обратно все знаки вопроса «?» на «0» или «1», чтобы получился код Грея.

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

Формат входных данных
В первой строке содержится целое число n — длина двоичных векторов. Следующие 2ⁿ строк содержат двоичные вектора длины n, в каждом из которых ровно один символ заменен на знак вопроса «?».
Формат выходных данных
В первой строке выведите «YES», если решение существует, и «NO» — в противном случае. В случае положительного ответа выведите исходный код Грея, если возможных вариантов ответа несколько, выведите любой.
 

Ввод	Вывод
2 0? 0? 1? 1?	YES 00 01 11 10
3 ?00 0?1 01? 0?0 ?10 1?1 10? 1?1	NO

Система оценки
 

Номер подзадачи	Баллы	Ограничения	Комментарии
1	37	1<=n<=4	Баллы начисляются, если все тесты пройдены.
2	63	1<=n<=12	Баллы начисляются, если все тесты этой и предыду- щих подзадач пройдены.

 

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

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

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

Вера решила для себя, что она будет действовать по самому справедливому принципу «считалочки»: она будет играть с одной из двух команд, играющих матч с соответствую- щем считалке номером K. Но затем Вера поняла, что уже выбрала себе команду, в которой хотела бы играть, причем ориентируясь не только на ее силу. Ей известны Q считалок, соответствующих различным значениям K. Для каждого из этих чисел K_i необходимо узнать, а кто же именно будет сражаться за столь ценный приз, то есть какие две коман- ды будут играть в матче с номером K_i.

Формат входного файла
Первая строка входных данных содержит единственное целое число N — количество команд (2 <= N <= 100 000). Вторая строка содержит N различных чисел от 1 до N — силы команд: первое число — сила команды, стоящей в начале очереди, второе — сила следующей по очереди команды, ..., последнее — сила команды, стоящей в конце очереди. Третья строка содержит единственное целое число Q (1 <= Q <= 100 000) — коли- чество известных Вере считалок. Каждая из следующих Q строк содержит число Ki (1 <= K_i <= 10¹⁸) — номер очередного интересующего Веру матча. Обратите внимание, Ki может быть больше N. Формат выходного файла Выведите Q строк: для каждого интересующего Веру числа K_i два числа в любом порядке — силы команд, сыграющих на K_i-м шаге. Первая строка должна содержать ответ на первый запрос, вторая — на второй и так далее.

Примеры

Ввод	Вывод
4 1 3 2 4 1 3	3 4
4 2 1 4 3 3 1 5 2	2 1 4 2 2 4

Комментарии
Разберем первый тест из условия:

	Кто играет	Состояние очереди	Победитель	Проигравший
Матч № 1 Матч № 2 Матч № 3	1 3 3 2 3 4	2 4 4 1 1 2	3 3 4	1 2 3

Таким образом, в единственном интересующем Веру третьем матче сыграют команды с силами 4 и 3.