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

Экран Рудольфа имеет размеры $$$(K \cdot H) \times (K \cdot W)$$$ пикселей. Пиксели экрана нумеруются сначала по вертикали числами от 0 до $$$(K \cdot H - 1)$$$ сверху вниз, затем по горизонтали — числами от 0 до $$$(K \cdot W - 1)$$$ слева направо. Таким образом, левый верхний угол экрана имеет координаты $$$(0; 0)$$$, а правый нижний — $$$(K \cdot H - 1; K \cdot W - 1)$$$.

Сначала Рудольф показал Байеру изображение, развёрнутое на весь экран. Затем Рудольф уменьшил изображение в $$$K$$$ раз; при этом левый верхний угол уменьшенного изображения оказался в координатах $$$(Y_F; X_F)$$$. Уменьшенное изображение целиком поместилось на экране.

Теперь Рудольф задаёт Байеру $$$Q$$$ вопросов следующего вида: «если на исходном изображении у пикселя были координаты $$$(Y_i; X_i)$$$, то какими будут его координаты на уменьшенном изображении?» Помогите Байеру правильно ответить на все вопросы.

Рудольф устроился на работу в подающий надежды IT-стартап, занимающийся разработкой весьма необычных сканеров. Сканеры нового поколения обрабатывают страницу особым образом — не по горизонтали или вертикали, а по диагонали. Каждая диагональ сканируется снизу вверх, а сами диагонали — слева направо:

Первое задание Рудольфа на новом месте — написать софт для диагонального сканера. По информации о пикселях диагоналей изображения Рудольфу нужно восстановить само исходное изображение. Помогите ему!

В ходе своих научных изысканий Рудольф наконец-то вывел полином, описывающий Самую Важную Закономерность!

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

• Запись полинома должна состоять из записей мономов вида c * x^p, разделённых операциями сложения и вычитания;
• Мономы, в которых коэффициент равен 0, не выводятся, но если весь полином тождественно равен 0, следует вывести 0;
• Моном степени 0 (свободный член) не должен содержать обозначения переменной;
• Коэффициенты при переменной и показатели степени, имеющие абсолютное значение 1, не выводятся;
• Знаки бинарных операций, за исключением возведения в степень, отделяются от операндов пробелами. Знаки унарного минуса и возведения в степень не отделяются пробелами.

Помогите Рудольфу получить текстовую запись имеющегося у него полинома.

Полгода Рудольф размышлял над концепцией логического устройства, которое поможет ему узнать ответ на Главный Вопрос Жизни, Вселенной и Всего Такого. Похоже, что ему наконец удалось учесть все-все нюансы, и он составил самую настоящую логическую схему!

При составлении логической схемы Рудольф руководствовался следующими правилами:

• Схема составляется на прямоугольном листе, разделённом на квадратные ячейки. В описании схемы каждой ячейке соответствует один символ;
• Символ $$$\texttt{.}$$$ обозначает пустую ячейку;
• Символ $$$\texttt{?}$$$ обозначает единственный выход логической схемы;
• Символы $$$\texttt{1}$$$ и $$$\texttt{0}$$$ обозначают константы ИСТИНА и ЛОЖЬ соответственно;
• Символы $$$\texttt{!}$$$, $$$\texttt{&}$$$ и $$$\texttt{|}$$$ обозначают логические элементы НЕ, И и ИЛИ соответственно;
• Каждый символ, обозначающий выход схемы, константу или логический элемент, окружён рамкой из 8 символов $$$\texttt{#}$$$. Различные рамки не пересекаются и не касаются друг друга;
• Символы $$$\texttt{+}$$$ обозначают соединения между выходом, константами и логическими элементами. Каждое соединение представляет собой прямую или ломаную, продолжающуюся по клеткам, имеющим общие стороны. Начало и конец соединения имеют общие стороны с рамками. Соединения не содержат самопересечений, различные соединения не пересекаются и не касаются друг друга;
• Рамки выхода схемы и констант имеют 1 примыкающее соединение, рамки элементов НЕ — 2 примыкающих соединения, рамки элементов И и ИЛИ — 3 примыкающих соединения;
• Соединения различных объектов на схеме образуют связный неориентированный ациклический граф.

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

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

Элементами файловой системы являются файлы и папки. Каждый файл или папка размещаются внутри некоторой другой папки; единственным исключением из этого правила является корневая папка — для неё родительской папки не существует.

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

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

Помогите Рудольфу автоматизировать его работу с файловой системой.

Случилось страшное — Рудольф почти проспал начало собственной лекции! Сейчас он в спешке собирается, надеясь всё же успеть в университет.

На пути от дома Рудольфа до университета есть $$$N$$$ остановок общественного транспорта; дом Рудольфа находится у первой остановки, университет — у $$$N$$$-й. Таким образом, путь разделён на $$$(N - 1)$$$ участков между последовательными остановками.

Каждый участок пути Рудольф может преодолеть либо пешком, либо на маршрутке:

• Если Рудольф преодолевает $$$i$$$-й участок пешком, то он тратит $$$A_i$$$ минут, а его усталость увеличивается на $$$X_i$$$ единиц;
• Если Рудольф преодолевает $$$i$$$-й участок на маршрутке, то он тратит $$$B_i$$$ минут и $$$Y_i$$$ рублей (обратите внимание, что для каждого участка проезд оплачивается отдельно). Кроме того, в маршрутке Рудольф отдыхает, в результате чего его усталость становится равной 0.

Лекция Рудольфа должна начаться через $$$T$$$ минут, а в кармане спешно надетой куртки он нашёл $$$C$$$ рублей, которые может потратить на оплату маршруток.

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

Рудольфу подарили шкатулку с необычным замком-головоломкой. Замок представляет собой квадратную сетку размера $$$N \times N$$$, в каждой клетке которой находится лампочка.

Горизонтальные ряды лампочек нумеруются числами от $$$1$$$ до $$$N$$$ сверху вниз, вертикальные — числами от $$$1$$$ до $$$N$$$ слева направо. Таким образом, например, лампочка в верхнем правом углу имеет координаты $$$(1; N)$$$, а лампочка в нижнем левом углу — $$$(N; 1)$$$.

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

Шкатулка откроется, если Рудольф сможет зажечь все лампочки. Помогите ему понять, на какие из них для этого нужно нажать.

Обратите внимание, что минимизировать количество ходов не требуется, но Рудольф должен сделать не более $$$1000$$$ ходов.

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

Внутри аквариума есть $$$N$$$ поперечных перегородок, расположенных на равных расстояниях друг от друга и от стенок аквариума. Перегородки пронумерованы слева направо числами от $$$0$$$ до $$$(N - 1)$$$; высота $$$i$$$-й перегородки равна $$$H_i$$$. Высота боковых стенок аквариума очень велика; фактически, её можно считать неограниченной.

Пространство, ограниченное соседними перегородками или боковыми стенками аквариума, будем называть сектором. Нетрудно видеть, что аквариум оказывается разделён на $$$(N + 1)$$$ секторов. Секторы нумеруются слева направо числами от $$$0$$$ до $$$N$$$.

Изначально аквариум не содержит воды.

В рамках своих экспериментов Рудольф выполняет два вида действий: либо доливает некоторый объём воды в определённый сектор, либо измеряет высоту столба воды в определённом секторе.

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

Помогите Рудольфу проконтролировать правильность его измерений.

У Байера сегодня день рождения. Рудольф решил порадовать своего питомца и купил ему его любимые конфетки M&M's. Байер очень обрадовался такому подарку, сразу же открыл пачку и высыпал разноцветные конфетки на стол.

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

Налюбовавшись на конфетки, Байер собрался съесть их все с чаем. Байер ест M&M's очень интересным способом: он выбирает интересную группу конфеток, съедает её и запивает одним глотком чая. Группа конфеток считается интересной, если количество конфеток каждого цвета в ней одинаково. Например, три красные и три синие конфетки формируют интересную группу, две синие, две зелёные и две жёлтые — тоже, а одна жёлтая и две красные — нет.

Рудольфу стало интересно, какое минимальное количество глотков чая потребуется Байеру, чтобы съесть и запить все конфетки. Помогите ему найти ответ на этот вопрос.

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

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

Ледовый шельф представляет собой квадратную область размера $$$N \times N$$$, разделённую на участки $$$1 \times 1$$$. Участки нумеруются по горизонтали числами от $$$0$$$ до $$$(N - 1)$$$ с запада на восток, по вертикали — числами от $$$0$$$ до $$$(N - 1)$$$ с севера на юг. Таким образом, участок в северо-восточном углу шельфа имеет координаты $$$(N - 1; 0)$$$, а в юго-западном — $$$(0; N - 1)$$$.

Некоторые из участков могут содержать ледяные разломы. Миссия марсохода — составить карту этих разломов на всём шельфе.

Марсоход будет спущен на шельф в участке с координатами $$$(X_S; Y_S)$$$. Он должен исследовать местность, а затем добраться до участка с координатами $$$(X_E; Y_E)$$$ для эвакуации. Стартовый и конечный участки не содержат разломов, от стартового участка марсоход может добраться до конечного, а также до всех участков с разломами, перемещаясь по участкам, соседним по стороне.

Марсоход может выполнять следующие команды перемещения:

• $$$\texttt{1 K}$$$ — переместиться на $$$K$$$ участков севернее;
• $$$\texttt{2 K}$$$ — переместиться на $$$K$$$ участков восточнее;
• $$$\texttt{3 K}$$$ — переместиться на $$$K$$$ участков южнее;
• $$$\texttt{4 K}$$$ — переместиться на $$$K$$$ участков западнее.

  Марсоход не может выезжать за границы шельфа или заезжать на участки с ледяными разломами. В ответ на любую корректную команду перемещения марсоход возвращает сообщение $$$\texttt{OK}$$$. Некорректная команда перемещения приведёт к провалу миссии.

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

• $$$\texttt{10}$$$ — узнать количество ледяных разломов на участках, соседних по стороне или углу с тем участком, в котором сейчас находится марсоход.

  В ответ на команду $$$\texttt{10}$$$ марсоход возвращает целое число от $$$0$$$ до $$$8$$$;

• $$$\texttt{100 X Y}$$$ — узнать количество ледяных разломов на участках, соседних по стороне или углу с участком, имеющим координаты $$$(X; Y)$$$. Сам этот участок обязан быть соседним по стороне с тем участком, в котором сейчас находится марсоход.

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

  В ответ на корректную команду $$$\texttt{100}$$$ марсоход возвращает целое число от $$$\texttt{0}$$$ до $$$\texttt{8}$$$, либо сообщение $$$\texttt{DANGER}$$$, если сам участок с координатами $$$(X; Y)$$$ содержит разлом. Некорректная команда $$$\texttt{100}$$$ приведёт к провалу миссии.

Наконец, когда марсоход завершит свою работу и будет готов к эвакуации, он должен выполнить последнюю команду:

• $$$\texttt{0}$$$ — завершить миссию. После этой команды следует вывести $$$N$$$ строк, каждая из которых содержит по $$$N$$$ символов $$$\texttt{.}$$$ или $$$\texttt{*}$$$ — карту шельфа. Символы $$$\texttt{.}$$$ должны соответствовать участкам без разломов, $$$\texttt{*}$$$ — участкам с разломами.

В настоящее время марсоход тестируют на испытательном полигоне. Помогите Рудольфу управлять его творением!

Первая строка стандартного потока ввода содержит целое число $$$N$$$ ($$$1 \le N \le 10$$$) — размер ледового шельфа.

Вторая строка стандартного потока ввода содержит четыре целых числа $$$X_S$$$, $$$Y_S$$$, $$$X_E$$$, $$$Y_E$$$ ($$$0 \le X_S, Y_S, X_E, Y_E \le N - 1$$$) — соответственно координаты участков старта и эвакуации.

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

• $$$\texttt{fflush(stdout)}$$$ в C++;
• $$$\texttt{System.out.flush()}$$$ в Java;
• $$$\texttt{stdout.flush()}$$$ в Python.

Если будет выведена некорректная команда, решение получит вердикт «Неправильный ответ». Если команда не будет выведена или не будет сброшен буфер вывода, решение получит вердикт «Решение зависло».

После вывода команды, отличной от команды $$$\texttt{0}$$$, программа должна считать из стандартного потока ввода ответ марсохода в описанном выше формате.

После вывода команды $$$\texttt{0}$$$ программа должна завершить работу.