В городе Новый Нижгород открылась новая служба доставки еды с оригинальным названием <<Камосат>>. Курьеры этой службы передвигаются на самокатах и стремятся максимально эффективно доставлять заказы клиентам.

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

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

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

Формат входных данных
Первая строка содержит одно целое число \(n\) (\(2 \leq n \leq 300\,000\)) — количество точек в городе.

Вторая строка содержит \(n\) целых чисел \(h_1, h_2, \ldots, h_n\) (\(-10^9 \leq h_i \leq 10^9\)) — высоты точек города.

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

Замечание

В первом примере курьер может стартовать в третьей точке с высотой \(6\) и проехать по высотам \(6\rightarrow2\rightarrow1\).

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

В третьем примере курьер может проехать по высотам \(5\rightarrow2\rightarrow3\rightarrow4\).

Текстовый файл состоит не более чем из 10⁷ символов и содержит только заглавные буквы A, B, C, D. Определите максимальную длину подстроки, состоящей из идущих групп символов ABCD в указанном порядке. При этом в начале и конце искомой последовательности группа символов ABCD может быть неполной. Искомая подстрока должна содержать не менее одной полной группы символов ABCD.

Например, условию задачи удовлетворяют: BCDABCDABCDA, DABCDABCDAB

Для выполнения этого задания следует написать программу. 

В ходе работы над оптимизацией компилятора для процессора из предыдущей задачи в фирме Хардсофт задумались об автоматическом выборе подпрограмм, которые станут инлайнподпрограммами. Инлайн-подпрограммы - это такой способ сборки машинного кода, при котором тело подпрограммы во время компиляции подставляется непосредственно в место её вызова, и оно становится частью вызывающего кода. Таким образом, исключаются накладные расходы на вызов и завершение подпрограмм во время работы. 
Инженеры фирмы Хардсофт считают, что инлайн-подпрограммами надо делать те, которые вызываются чаще всего. Однако вставка кода больших подпрограмм в места их вызова приведёт к резкому увеличению памяти, потребляемой программами, а для фирмы важна возможность лёгкой адаптации своего решения к промышленным устройствам, в которых значительную роль играет экономическая составляющая: в частности, необходимый для работы объём памяти должен быть минимальным.
Разработчики создали специальный анализатор, который определяет среднее количество запуска подпрограмм и размер каждой из них.
Требуется определить, какие из подпрограмм можно встроить в инлайн-режиме, для увеличения быстродействия и в пределах доступной памяти.

Формат входных данных
в первой строке через пробел указаны натуральные числа N, M и X. N и M не превышают 100 и являются количеством подпрограмм и количеством цепочек вызова, а X не превышает 10⁶ и является количеством памяти (в килобайтах), доступным для размещения инлайнподпрограмм. Далее идёт N строк, где через пробел перечислены имена подпрограмм (из латинских слов длиной до 20 символов) и их размер в килобайтах (натуральное число от 1 до 1000). Далее - M строк с описанием выявленных цепочек вызова: в них записаны имена подпрограмм через пробел, после которых также через пробел указано ожидаемое количество срабатываний этой цепочки за время работы программы (целое число от 1 до 1000).
Формат выходных данных
в первой строке - количество подпрограмм, которые можно пометить инлайновыми, в последующих строках - имена этих подпрограмм в том порядке, в котором они были указаны во входных данных. Требуется выбрать подпрограммы так, чтобы количество вызовов инлайн-подпрограмм за время работы программы было максимальным. 

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

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

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

Робот может перемещаться только по тротуарам и пешеходным переходам. Для определения цвета светофора робот обладает камерой с разрешением \(h \times w\) (где \(w\) четно). Для управления роботом вы можете передавать ему следующие команды:

• <<turn \(c\)>>, где \(c \in \{\text{`{L}'}, \text{`{U}'}, \text{`{R}'}, \text{`{D}'}\}\), означает поворот в соответствующую сторону (влево, вверх, вправо или вниз);

• <<move>> означает перемещение на одну клетку вперед относительно текущего направления;

• <<camera>> означает получение изображения с камеры; в ответ на эту команду вы получаете таблицу из \(h \times w\) символов, каждый из которых описывает преобладающий цвет (‘r’, ‘g’ или ‘b’ — красный, зеленый или синий) в соответствующей области пространства перед роботом;

• <<wait \(t\)>> означает ожидание в течение \(t\) секунд.

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

Светофоры могут находиться на разной высоте и на разном расстоянии сбоку от соответствующего перехода. Если робот находится около перехода с \(i\)-м светофором и смотрит в его направлении, на изображении с камеры светофор будет занимать две клетки в \(a_i\)-й и \((a_i + 1)\)-й снизу строках в столбце на расстоянии \(b_i\) от центра (слева от центра, если \(b_i < 0\), и справа, если \(b_i > 0\)). Для светофора, горящего красным, нижняя из этих двух клеток равна ‘b’, а верхняя равна ‘r’. Для зеленого светофора нижняя клетка равна ‘g’, а верхняя — ‘b’. Остальные клетки на изображении могут любого из трех цветов.

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

Напишите программу, сообщающую роботу команды, безопасно приводящие его из стартовой клетки в конечную. Минимизировать затраченное в пути время не требуется. В изначальной клетке робот находится в направлении <<вверх>> (‘U’).

Каждый тест состоит из нескольких наборов входных данных. В первой строке ввода дано единственное целое число \(t\) — количество наборов входных данных в тесте (\(1 \le t \le 50\)).

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

В первой строке описания карты даны два целых числа \(n\) и \(m\) — размеры карты (\(1 \le n, m \le 50\)). Следующие \(n\) строк содержат по \(m\) символов каждая и описывают карту. Символ на \(j\)-й позиции \(i\)-й строки описывает клетку с координатами \((i, j)\) и равен ‘.’, если это клетка тротуара, и ‘+’, если это клетка проезжей части.

В следующей строке даны три целых числа \(k\), \(h\) и \(w\) — количество переходов со светофорами и разрешение камеры, соответственно (\(k \le n \cdot m\); \(2 \le h, w \le 8\); \(w\) четно).

Следующие \(3k\) строк описывают светофоры: по три на каждый из \(k\) переходов. В первой строке для \(i\)-го светофора дано положение соответствующего ему перехода \((r_i, c_i)\) (\(1 \le r_i \le n\); \(1 \le c_i \le m\)). Во второй строке дано описание светофора с одного из двух концов перехода в формате <<\(d_{i,1}\) \(a_{i,1}\) \(b_{i,2}\)>>, где \(d_1\) указывает на направление перехода, соответствующее этому светофору, а \(a_{i,1}\) и \(b_{i,1}\) — его высота и расстояние от центра перехода, соответственно (\(d_{i,1} \in \{\text{`{L}'}, \text{`{U}'}, \text{`{R}'}, \text{`{D}'}\}\); \(1 \le a_{i,1} < h\); \(1 \le |b_{i,1}| \le \frac{w}{2}\)). В третьей строке в том же формате описывается светофор с противоположной стороны перехода.

Наконец, в последней строке набора входных данных даны четыре целых числа \(i_1\), \(j_1\), \(i_2\) и \(j_2\) — координаты стартовой и конечной клеток, соответственно (\(1 \le i_1, i_2 \le n\); \(1 \le j_1, j_2 \le m\)).

Гарантируется, что все \((r_i, c_i)\) различны, а описания светофоров корректны: направления \(d_{i,1}\) и \(d_{i,2}\), указанные во вводе, противоположны и соответствуют направлениям, в которых от этого перехода расположен тротуар. Также гарантируется, что конечная клетка достижима из стартовой.

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

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

• Чтобы повернуть робота, выведите <<turn \(c\)>>, где \(c \in \{\text{`{L}'}, \text{`{U}'}, \text{`{R}'}, \text{`{D}'}\}\). В результате выполнения этого действия робот повернется <<лицом>> в соответствующем направлении, и интерактор выведет <<OK>> на отдельной строке.

• Чтобы переместить робота, выведите <<move>>. В таком случае робот переместится на одну клетку вперед в том направлении, в котором он повернут. Если это действие успешно, интерактор выведет <<OK>> на отдельной строке. Если при этом робот достиг конечной клетки \((i_2, j_2)\), интерактор перейдет к рассмотрению следующего набора входных данных и подаст соответствующие входные данные на ввод вашей программе (либо завершится и засчитает ваше решение, если это был последний набор входных данных).

  Если же робот при таком перемещении попадает в непроходимую клетку, выходит за пределы карты или выезжает на пешеходный переход на красный свет, интерактор выведет <<FAIL>> и завершится с вердиктом Wrong Answer. Во избежание получения некорректного вердикта, считав <<FAIL>>, ваше решение также должно завершиться.

• Чтобы сделать снимок, выведите <<camera>>. В ответ интерактор выведет \(h\) строк по \(w\) символов каждая. Каждый символ равен ‘r’, ‘g’ или ‘b’ и задает цвет соответствующего <<пикселя>>. Если непосредственно перед роботом не находится пешеходный переход, все символы будут случайными. Если же робот стоит у перехода, то два символа, соответствующие положению на <<изображении>> светофора напротив, будут отражать цвет этого светофора как описано в условии.

• Чтобы подождать \(t\) секунд (\(1 \le t \le 2 \cdot 10^6\)), выведите <<wait \(t\)>>. В ответ интерактор выведет <<OK>> на отдельной строке и обновит состояние всех светофоров, цвет которых за это время поменяется.

  Запрещается делать более \(25\) команд ожидания в одной и той же клетке поля. Если ваше решение совершает хотя бы \(26\) запросов ожидания из одной и той же клетки, интерактор в ответ выведет <<FAIL>> и завершится с вердиктом Wrong Answer.

Вывод каждой команды ваша программа должна завершать выводом символа перевода строки (endl, ‘\n’) и сбросом буфера вывода. Сбросить буфер можно с помощью

• <<fflush(stdout)>> в C и C++, или <<cout.flush()>> только в C++,

• <<System.out.flush()>> в Java,

• <<sys.stdout.flush()>> в Python,

• и <<Console.Out.Flush()>> в C#.

• В Pascal и Delphi сброс буфера при выводе в стандартный поток вывода происходит автоматически.

Решение, не выполняющее эти действия, может получить произвольный вердикт (скорее всего, Time Limit Exceeded или Idleness Limit Exceeded).

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

Пояснение к примеру

Во втором наборе входных данных в примере:

1. В клетке \((3, 2)\) нет перехода, поэтому по ней нельзя перемещаться;

2. При пересечении перехода в \((1, 2)\) в направлении ‘R’ светофор находится на высоте \(2\) и на расстоянии \(-2\) от центра: соответственно, его клетки на изображении располагаются в первом столбце во второй и третьей снизу строках. Для данного снимка они равны ‘b’ в верхней строке и ‘g’ во второй, поэтому его сразу можно пересекать.

3. При пересечении перехода в \((2, 3)\) в направлении ‘D’ светофор находится на высоте \(1\) и на расстоянии \(2\) от центра, то есть в четвертом столбце в двух нижних строках. На первом изображении он горит красным, а после ожидания (<<wait 10>>) — зеленым.

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

Глубина ямы равна H. Каждый школьник знает свой рост по плечи h_i и длину своих рук l_i. Таким образом, если он, стоя на дне ямы, поднимет руки, то его ладони окажутся на высоте h_i + l_i от уровня дна ямы. Школьники могут, вставая друг другу на плечи, образовывать вертикальную колонну. При этом любой школьник может встать на плечи любого другого школьника. Если под школьником i стоят школьники j₁, j₂, …, j_k, то он может дотянуться до уровня h_j1 + h_j2 + … + h_jk + h_i + l_i.

Если школьник может дотянуться до края ямы (то есть h_j1 + h_j2 + … + h_jk + h_i + l_i ≥ H), то он может выбраться из нее. Выбравшиеся из ямы школьники не могут помочь оставшимся.

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

Формат входных данных
В первой строке входных данных задается натуральное число N (1 ≤ N ≤ 2000) — количество школьников, попавших в яму.

Далее в N строках содержится по два целых числа: рост i-го школьника по плечи h_i (1 ≤ h_i ≤ 10⁵) и длина его рук l_i (1 ≤ l_i ≤ 10⁵).

В последней строке указано целое число — глубина ямы H (1 ≤ H ≤ 10⁵).

Формат выходных данных
В первой строке выведите K — максимальное количество школьников, которые смогут выбраться из ямы. Если K > 0, то во второй строке в произвольном порядке выведите их номера, разделяя их пробелами. Школьники нумеруются с единицы в том порядке, в котором они заданы во входных данных. Если существует несколько решений, выведите любое.

Определите наибольшее целое значение A, при котором найдутся такие целые неотрицательные x и y, при которых значение выражения ложно?
 

Банк «Кисловодск» переходит на новый вид банковских карт. Для этого производятся одинаковые заготовки, на которых есть специальное место для идентификации клиента. Изначально на этом месте записывается кодовое число X. В банке с помощью специального прибора можно стирать некоторые цифры числа X. Оставшиеся цифры, будучи записанными подряд, должны образовывать номер счета клиента. Например, при X = 12013456789 номера счетов 5, 12, 17 или 12013456789 получить можно, а номера 22 или 71 получить нельзя.

Способ распределения номеров счетов в банке очень прост. Счетам присваиваются последовательно номера 1, 2, … Очевидно, что при таком способе в какой-то момент впервые найдется номер счета N, который нельзя будет получить из цифр X указанным выше способом. Руководство банка хочет знать значение N.

Напишите программу, которая находила бы N по заданному X.

Формат входных данных
Вводится натуральное число X без ведущих нулей (1 ≤ X ≤ 101000). 

Формат выходных данных
Выведите искомое N без ведущих нулей.

Определите наибольшее целое значение A, при котором найдутся такие целые неотрицательные x и y, при которых значение выражения ложно?
 

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч {1} либо увеличить количество камней в куче в два раза. Для того, чтобы делать ходы, у каждого игрока есть неограниченное количество камней. 
Игра завершается в тот момент когда суммарное количество камней в кучах становится не менее {2}. 
Победителем считается игрок, сделавший последний ход, т.е. первым получивший суммарно в кучах {2} или больше камней.
В начальный момент в первой куче было {3} камней, во второй - S камней; 1 <= S <= {4}.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. 

Задание 19
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимательное значение S, при котором такая ситуация возможна.

Задание 20
Найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причем одновременно выполняются два условия: 
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. 
 Найденные значения запишите в порядке возрастания.

Задание 21
Найдите минимальное значение S, при котором одновременно выполняются два условия: 
- У Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом, при любой игре Пети;
- У Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. 
 Если найдено несколько значений S, в ответе укажите наименьшее из них.


Ответ на каждое задание вводите в отдельной строке. Несколько значений в одной строке разделяйте одним пробелом.

Вам дан массив A из N чисел. Найдите количество различных пар (i, j), таких, что j>=i и A[i] = A[j].

Формат входных данных
Первая строка входных данных содержит количество тестовых случаев T. Каждый тестовый случай состоит из двух строк, первая строка - число N, за ней следует строка, состоящая из N целых чисел, которые являются элементами массива A.

Ограничения
1 <= T <= 10
1 <= N <= 106 
-106 <= A[i] <= 106
0 <= i < N

Формат выходных данных
Для каждого тестового случая выведите количество различных пар.
 

Прямоугольник ABCD задан координатами своих вершин. На противоположных сторонах AB и CD заданы последовательности R1 и R2 из N точек разбиения, а на сторонах BC и AD - R3 и R4 из M точек разбиения. Нумерация элементов последовательностей R1 и R2 начинается соответственно от точек A и D, а R3 и R4 - от точек B и A. Соединив отрезками точки с одинаковыми номерами в разбиениях R1 и R2, а затем в разбиениях R3 и R4, получим разбиение Q прямоугольника ABCD на множество четырехугольников.
Построить алгоритм, определяющий четырехугольник разбиения Q с наибольшей площадью, при условии, что отрезки, соединяющие точки разбиений R1 и R2 параллельны стороне AD.
Последовательности R1, R2, R3 и R4 задаются как массивы из длин отрезков разбиения соответствующих сторон прямоугольника.
 

На физкультуре школьники 10-А класса играют в баскетбол. В классе учится \(n\) школьников, которые построились в ряд. Учитель физкультуры разделил их на две команды следующим образом: в первую команду пошли школьники, которые стоят на нечетных местах: первом, третьем, пятом, и т. д. Школьники, которые стоят на четных местах: втором, четвертом, шестом, и т. д. составили вторую команду.

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

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

Запасной же игрок, которые провел к этому моменту на поле меньше всего минут, выходит на поле. Если таких игроков несколько, на поле выходит игрок с минимальным номером в исходном построении.

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

Например, пусть исходно шесть учеников построились в следующем порядке: Иванов, Петров, Сидоров, Андреев, Казаков, Сергеев. Команды будут сформированы следующим образом. Первая команда: Иванов, Сидоров, Казаков. Вторая команда: Петров, Андреев, Сергеев. Пусть на поле одновременно находятся 2 игрока, тогда исходно на поле выйдут Иванов и Сидоров от первой команды, Петров и Андреев от второй.

После первой минуты игры Сидоров и Андреев пойдут на скамейку запасных, а на поле появятся Казаков и Сергеев. После второй минуты отдыхать пойдут Иванов и Петров, а Сидоров и Андреев вернутся на поле. Наконец, после третьей минуты Казаков и Сергеев снова пойдут отдыхать, а на площадке появятся Сидоров и Андреев. Таким образом после трех смен на поле будут (в алфавитном порядке) Андреев, Иванов, Петров и Сидоров.

Формат входных данных
Первая строка содержит три целых числа: \(n\), \(m\) и \(p\) (\(2p \le n \le 50\), \(1 \le p \le 10\), \(0 \le m \le 100\)). Следующие с \(n\) строк содержат по одной фамилии — игроки в том порядке, в котором они исходно построились Каждая фамилия представляет собой непустую последовательность букв латинского алфавита не длиннее 50. Все фамилии различны.

Формат выходных данных
Выведите в алфавитном порядке фамилии игроков, которые будут на поле после \(m\) смен составов. Разделяйте фамилии пробелом.

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

Например, если \(n = 20\), то искомое число — 12, у него 6 делителей: 1, 2, 3, 4, 6 и 12.

Формат входных данных
На вход подается одно число \(n\) (\(1 \le n \le 100\,000\))

Формат выходных данных
Выведите на первой строке число от 1 до \(n\), включительно, которое имеет максимальное число делителей. На второй строке выведите число его делителей.

Если есть несколько чисел от 1 до \(n\) с максимальным числом делителей, выведите любое из них.

Задано четыре числа: \(a\), \(b\), \(c\) и \(d\). Требуется разбить их на две пары, чтобы сумма произведений в этих парах была максимальна.

Например, если заданы числа 2, 3, 4 и 5, то оптимально разбить их на пары \((2, 3)\) и \((4, 5)\), в этом случае искомая сумма равна \(2 \times 3 + 4 \times 5 = 26\).

Формат входных данных
На вход подаются четыре числа: \(a\), \(b\), \(c\) и \(d\). Все числа по модулю не превышают 1000.

Формат выходных данных
Выведите искомую максимальную сумму.

Операнды арифметического выражения записаны в системе счисления с основанием 27. В записи чисел переменной х обозначена неизвестная цифра из алфавита 27-ричной системы счисления. Определите наибольшее значение х, при котором значение данного арифметического выражения кратно 26. Для найденного значения х вычислите частное от деления значения арифметического выражения на 26 и укажите его в ответе в десятичной систем счисления. Основание системы счисления указывать не нужно.

Определите в 27-ричной записи числа количество цифр с числовым значением, превышающим 9:

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

Вася из задачи A по-прежнему занят поиском кладов. Более того, у него появились последователи. Один из таких последователей попросил Васю помочь в своих поисках. Так, по карте сокровищ Васю просят восстановить кратчайший путь до клада. Конфигурация лабиринта совпадает с конфигурацией, описанной в задаче A (поле \(N \times M (1 \le N, M \le 100, N \times M \le 100))\), в одной клетке которого находится клад, в K
 клетках находятся входы в лабиринт).

Требуется вывести искомый путь.

Формат входных данных
Первая строка содержит 2 числа N<=100 и M<=100, задающие размеры лабиринта. Далее следует описание лабиринта: N
 строк по M символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).
В (N+2)-й строке находится число \(K (1 \le K \le N \times M)\) - количество входов в лабиринт. Далее в K строках содержатся координаты входов. Так, в i-й строке содержатся числа \(x_i\) и \(y_i\), означающие, что i-й вход расположен в \(x_i\)-й строке и в \(y_i\)-м столбце \((1 \le x_i \le N, 1\le y_i \le M)\). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.

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

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

Примеры

№	Входные данные	Выходные данные
1	5 5 00000 00000 10*00 01111 00000 4 1 1 1 5 4 1 5 5	4 1 1 2 1 2 2 3 2 3 3
2	3 3 010 1*1 010 4 1 1 1 3 3 1 3 3	-1

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

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

Формат входных данных
Вам даны 8 целых чисел - \(x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4\), где \((x_1, y_1)\) - координаты левого нижнего угла рисунка Пети, \((x_2, y_2)\) - координаты правого верхнего угла рисунка. Аналогично, \((x_3, y_3)\) - координаты левого нижнего угла вырезанного Васей прямоугольника, \((x_4, y_4)\) - координаты правого верхнего угла вырезанного прямоугольника. Гарантируется, что данные прямоугольники невырождены (\(x_1 < x_2\), \(y_1 < y_2\) и аналогичные неравенства для второго набора координат). Листок был не очень большим, поэтому каждое число по модулю не превосходит \(10^4\).

Формат выходных данных
Выведите YES, если Вася испортил рисунок, и NO в противном случае.

Примечание

В городе Н. олимпиада по информатике состоит из двух туров, каждый из которых оценивается из 400 баллов. Для удобства все её участники занумерованы числами от 1 до \(N\).

Сразу после проведения олимпиады курьер принёс жюри пренеприятнейшее известие: <<сверху>> пришло указание о том, что некто Вася, выступавший в олимпиаде под номером 1, должен занять как можно более высокое место, то есть как можно меньше участников должны набрать по сумме двух туров больше баллов, чем Вася. При этом места, занятые школьниками в каждом из туров в отдельности, уже опубликованы, и их менять нельзя. Для каждого тура дан список номеров участников в порядке занятого места — перестановка чисел от 1 до \(N\). Теперь работа жюри заключается в том, чтобы расставить целые баллы от 1 до 400 каждому участнику в первом и втором турах таким образом, чтобы в итоговой таблице Вася занял как можно более высокое место, а места участников в каждом из туров не изменились. При этом никакие два участника не должны получить в одном туре одинаковые баллы.

Ваша задача — проделать за жюри такую работу.

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

Формат входных данных
Сначала вводится целое число \(N\) (\(1 \le N \le 200\)) — количество участников олимпиады. Во второй строке перечислены номера участников в порядке занятых мест в первом туре (от первого места до \(N\)-го). В третьей строке в таком же формате следует описание второго тура. Номера участников во второй и третьей строках разделены пробелами.

Формат выходных данных
Сначала выведите \(N\) целых чисел от 1 до 400, соответствующих расстановке баллов участникам первого тура, где \(i\)-ое число — балл в первом туре участника, занявшего на нём \(i\)-е место, затем аналогично \(N\) целых чисел, соответствующих расстановке баллов во втором туре. Числа разделяйте пробелами или переводами строки. Никакие два участника не должны получить одинаковые баллы в одном и том же туре. Если существует несколько способов расставить баллы требуемым образом, выведите любой из них.

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