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

ML (move left) – снять крайнюю левую бусинку и надеть ее на правый конец нитки. По сути, при этом происходит циклический сдвиг ожерелья.
MR (move right) – снять правую бусинку и надеть ее на левый конец.
RL (remove left) – снять крайнюю левую бусинку и положить ее на стол (не одевать на нитку).
RR (remove right) – снять крайнюю правую бусинку и положить ее на стол.
PL (put left) – взять со стола бусинку и надеть ее на левый конец нитки.
PR (put right) – взять со стола бусинку и надеть ее на правый конец нитки.

На столе может лежать не более одной снятой бусинки, то есть после операции RL или RR нельзя использовать другую операцию RL или RR, пока не будет выполнена операция PL или PR.

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

Входные данные
Программа получает на вход количество бусинок в ожерелье N ≤ 500. Далее идет некоторая перестановка чисел 1, . . . , N, задающая номера бусинок, расположенных на нитке. Номера перечислены слева направо.

Выходные данные
Программа должна вывести последовательность команд ML, MR, RL, RR, PL, PR, которая переводит исходную перестановку бусинок к перестановке 1, . . . , N.

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

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

Стопка определяется заданием диаметра каждой оладьи в стопке в порядке следования (сверху вниз). Переворачивание определяется количеством оладий, которое переворачивается. Например, из стопки 7 3 9 1 5 переворачиванием трех оладий получится стопка 9 3 7 1 5.

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

Входные данные
Первая строка входных данных содержит натуральное число N (1 ≤ N ≤ 1000)  – количество оладий в стопке. Далее идет N натуральных чисел, не превосходящих 10⁹  – размеры оладий в стопке (сверху вниз). 

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

При решении задач баллистики следует учитывать сопротивление воздуха. Пусть сила сопротивления воздуха пропорциональна квадрату модуля скорости движения снаряда и направлена противоположно скорости. Считая коэффициент пропорциональности силы сопротивления воздуха квадрату скорости постоянной величиной, рассчитать дальность полёта снаряда (с точностью до 10 м) при стрельбе из 85-миллиметровой пушки Д-44 под заданным углом к горизонту, если масса снаряда равна 9.6 кг, а начальная скорость - 800 м/с. Известно также, что при стрельбе под углом 45 градусов дальность стрельбы составляет 15 650 м. Ускорение свободного падения считать равным 9.8 м/с².

Ограничения: угол от 5 до 85 градусов.

Входные данные
В первой строке находится единственное вещественное число - угол в градусах.

Выходные данные
Вывести одно целое число - дальность в метрах.

Ограниченный алгоритм Маркова состоит из последовательности предложений где s_i и d_i - символы из алфавита A, B, C. Подстрока s₁s₂...s_N называется левой частью, а d₁d₂...d_N - правой частью предложения.

Алгоритм выполняется над исходной текстовой строкой, состоящей из прописных латинских букв A, B, C, следующим образом: перебираются все предложения, начиная с первого. Если левая часть предложения входит в текстовую строку, то самое левое вхождение заменяется правой частью этого предложения, и поиск вновь начинается с первого предложения. Если ни одно предложение не может быть применено, алгоритм останавливается.

При выполнении алгоритма возможны два результата: либо остановка, либо бесконечный цикл с определенным периодом. По данной строке и набору предложений алгоритма Маркова определить количество "ациклических" (выполненных до начала цикла) шагов и длину самого цикла. Если алгоритм останавливается, то длина цикла считается нулевой, а все выполненные шаги - ациклическими.

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

Ограничения: длина исходной текстовой строки и левых частей предложений - от 1 до 12 букв, количество предложений - от 1 до 50.

Выходные данные
Вывести два целых числа, разделённых пробелом - количество ациклических шагов и длину цикла.

Напишите программу, реализующую сложение, вычитание, умножение и деление дробей. Формат дробей во входных и выходных данных:

• знак числа (пишется только в случае, когда его отсутствие изменяет число);
• целая часть числа (нулевая целая часть не пишется, если есть числитель и знаменатель);
• пробел (не пишется, если отсутствует целая или дробная часть);
• числитель (если он не равен нулю);
• знак / (если есть числитель);
• знаменатель (если есть числитель).

Примеры представления дробных чисел: -7 3/4, 8 1/2, -7/11, 0, 11.

Ограничения (как на входные, так и на выходные данные): целая часть может принимать значения из диапазона 0...30 000, числитель и знаменатель могут принимать значения от 1 до 30 000, при делении второй операнд не равен нулю.

Входные данные
В первой строке вводится дробь (первый операнд), во второй - знак операции ("+" - сложение, "-" - вычитание, "*" - умножение, "/" - деление), в третьей строке - дробь (второй операнд). Обе дроби могут быть сократимы.

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

В игру «черный ящик» играют с помощью квадратного черного ящика, который располагается на плоском столе. На каждой из сторон ящика есть n отверстий (всего 4n отверстий), в которые можно вбрасывать шар. Вброшенный шар через некоторое время вылетит наружу через одно из 4n отверстий, возможно, через то же отверстие, в которое он был вброшен.



Содержимое черного ящика можно рассматривать в виде сетки размером n x n. Отверстия в сторонах ящика – это начала и концы строк и столбцов сетки. Каждая клетка сетки либо пустая, либо занята отражателем. Отражатель – это устройство, которое изменяет направление движения шара на 90 градусов. Рассмотрим пример ящика размером 5x 5.

Вброшенный шар движется по прямой, пока не попадает в отражатель или не вылетит наружу. Когда шар попадает в отражатель, шар меняет направление своего движения, а отражатель меняет свое положение (под словом «меняет» подразумевается поворот на 90 градусов). На примере показаны действия отражателя.



a) Первый шар вброшен через отверстие. Он попал в отражатель и изменил направление движения.

b) После попадания первого шара отражатель изменил свое положение. Новый шар вбросили в то же отверстие, он попал в тот же отражатель, и отразился в направлении, противоположном направлению первого шара после отражения.

c) Отражатель изменил свое положение. После каждого попадания положение отражателя изменяется.


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

ЗАДАНИЕ
Вам будет предоставлен интерфейс к 15 черным ящикам с помощью библиотеки функций Pascal или C/C++. Вы должны определить содержимое каждого из ящиков как можно точнее и отправить на проверку файлы, описывающие каждый ящик. Интерфейс также предоставляет возможность создания собственных ящиков для тестирования.

ОГРАНИЧЕНИЯ
1 ≤ n ≤ 30

 

ВЫВОД

Вы должны предоставить на проверку файлы, содержащие следующие данные для каждого из 15 черных ящиков:

blackboxK.out

ОПИСАНИЕ

#FILE blackbox K ..... .../. .... .../. .?.?.

СТРОКА 1: Заголовок файла, который должен иметь вид #FILE blackbox K где K (число в диапазоне 1..15) соответствует ящику, для которого найдено решение. n СТРОК: Каждая строка описывает строку ящика, начиная с верхней и заканчивая нижней. Каждая строка должна содержать ровно n символов, соответствующих клеткам, находящимся на пересечении этой строки и столбцов (слева направо). ·Символ ‘.’ обозначает, что клетка пуста. ·Символ ‘/’ обозначает, что в клетке находится отражатель с исходным положением ‘/’ ·Символ ‘’ обозначает, что в клетке находится отражатель с исходным положением ‘’ ·Символ ‘?’ обозначает, что Вы не смогли определить исходное содержимое клетки

 

БИБЛИОТЕКА

Вам будет предоставлена библиотека, которая содержит следующие функции:

ФУНКЦИЯ	Описание
PASCAL function Initialize(box: integer): integer; C/C++ int Initialize(int box);	Инициализирует библиотеку. Эта функция должна вызываться один раз в начале программы. Она возвращает значение n – количество отверстий на каждой стороне ящика. Параметр box должен содержать целое число в пределах от 1 до 15, указывающее номер ящика, который Вы хотите использовать, или 0, если Вы хотите использовать ящик, созданный Вами.
PASCAL function throwBall(holeIn, sideIn: integer; var holeOut, sideOut: integer): longint; C int throwBall(int holeIn, int sideIn, int *holeOut, int *sideOut); C++ int throwBall(int holeIn, int sideIn, int &holeOut, int &sideOut);	Вбрасывает шар в ящик через отверстие с номером holeIn на стороне sideIn. Стороны пронумерованы следующим образом: 1 – Верхняя, 2 – Правая, 3 – Нижняя и 4 – Левая. Отверстия пронумерованы слева направо и сверху вниз, начиная с номера 1 на каждой стороне. В параметрах holeOut и sideOut функция возвращает номер отверстия и номер стороны – место, где шар вылетел наружу. В качестве своего значения функция throwBall возвращает количество звуковых сигналов, вызванных попаданиями шара в отражатели.
PASCAL procedure ResetBox; C/C++ Void ResetBox();	Возвращает все отражатели в исходное положение.
PASCAL procedure ToggleDeflectors; C/C++ Void ToggleDeflectors();	Меняет положения всех отражателей в ящике на противоположные.
PASCAL procedure Finalize; C/C++ Void Finalize();	Корректно заканчивает взаимодействие с ящиком. Эта функция должна вызываться в конце Вашей программы.

Чтобы использовать библиотеку в Вашей программе, необходимо выполнить следующее:
·FreePascal: В каталоге задачи есть файлы pbblib .o и pbblib. ppu. Чтобы их использовать, необходимо добавить следующую строку в Вашу программу
uses pbblib;
В файле pblackbox.pas представлен пример использования библиотеки.

·C: В каталоге задачи есть файлы cbblib.o и cbblib.h. Чтобы их использовать, необходимо добавить следующую директиву в Вашу программу
#include “cbblib.h”
В файле cblackbox.c представлен пример использования библиотеки. Чтобы скомпилировать код, используйте следующую команду
gcc –o yourprogram cbblib.o yourprogram.c

·C++: В каталоге задачи есть файлы cppbblib.o и cppbblib.h. Чтобы их использовать, необходимо добавить следующую директиву в Вашу программу
#include “cppbblib.h”
В файле cppblackbox .cpp представлен пример использования библиотеки. Чтобы скомпилировать код, используйте следующую команду
g++ –o yourprogram cppbblib.o yourprogram.cpp

 

ЗАМЕЧАНИЕ: В любой момент времени может быть запущено не более одной программы, работающей с библиотекой.
 

ПРИМЕР ВЗАИМОДЕЙСТВИЯ

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

ВЫЗОВ ФУНКЦИИ	ВОЗВРАЩЕННОЕ ЗНАЧЕНИЕ
Initialize(0);	Пусть программа взаимодействует с ящиком, изображенным на рисунке. Тогда функция возвращает значение 5, означая, что n = 5.
PASCAL throwBall(3,4,holeOut,sideOut ); C throwBall(3,4,&holeOut,&sideOut); C++ throwBall(3,4,holeOut,sideOut);	Шар вбрасывается в отверстие с номером 3 (третье сверху) на левой стороне. Возвращается значение 1 – это означает, что шар отразился один раз. После возврата из функции, переменная holeOut содержит значение 2, а переменная sideOut содержит значение 3, то есть шар вылетел через отверстие с номером 2 (второе слева) нижней стороны ящика.

ЭКСПЕРИМЕНТИРОВАНИЕ
Если Вы передадите значение 0 в функцию Initialize, библиотека прочитает содержимое ящика из файла blackbox.in. Так Вы сможете экспериментировать с библиотекой. Формат файла blackbox.in описан ниже.

blackbox.in

ОПИСАНИЕ

5 3 2 3 4 2 / 4 4 /

СТРОКА 1: Содержит целое число n, которое задает количество отверстий на каждой стороне. СТРОКА 2: Содержит целое число d , которое задает количество отражателей в ящике. СЛЕДУЮЩИЕ d СТРОК: Каждый отражатель описывается одной строкой. Каждая строка содержит два целых числа, разделенных пробелом, которые задают номер столбца и строки, где расположен отражатель. После второго числа через один пробел записан символ, который может быть ‘/’ или ‘’ и определяет исходное положение отражателя.

ЗАМЕЧАНИЕ: Файл blackbox. in из примера описывает ящик, изображенный вверху страницы 1.
 

СООБЩЕНИЯ ОБ ОШИБКАХ

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

СООБЩЕНИЕ	ЗНАЧЕНИЕ
ERR 1 More than one app	Только одна программа может одновременно работать с черными ящиками, перезапустите все программы и запускайте их строго по одной.
ERR 2 Invalid box	Переданный вами номер ящика не лежит в пределах от 0 до 15.
ERR 3 Invalid deflector	В файле blackbox.in находится отражатель в некорректной клетке.
ERR 4 Invalid symbol	В файле blackbox.in обнаружен недопустимый символ.
ERR 5 Invalid size	Размер ящика в файле blackbox. in задан неверно.
ERR 6 Invalid input hole	Либо сторона, либо отверстие вбрасывания шара заданы неверно.
ERR 7 ALARM	Пожалуйста, обратитесь к техническому персоналу.

 

«Соединение точек» – это игра для одного игрока. Игровое поле строится следующим образом. Выбираются два целых числа, каждое из которых больше 2, которые обозначаются g и r. Затем на плоскости рисуются четыре точки в вершинах квадрата, две верхние из них становятся зелеными точками, а две нижние – красными. Далее внутри квадрата рисуются зеленые и красные точки таким образом, что никакие три точки, включая вершины квадрата, не лежат на одной прямой. Процесс продолжается до тех пор, пока общее количество зеленых точек не станет равным g, а количество красных точек – равным r.

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

Будем считать, что две точки u и v принадлежат одной компоненте, если от u до v можно дойти по нарисованным отрезкам.

Цель игры – соединить все зеленые точки в одну компоненту с помощью (g – 1) отрезков, а все красные точки – в другую компоненту с помощью (r – 1) отрезков. Можно доказать, что при вышеописанном способе расположения точек всегда существует способ выиграть игру.

Вам будет задано квадратное игровое поле со стороной s, а также g зелеными и r красными точками. Координаты точек задаются парами целых чисел (x_i, y_i). Зеленые точки пронумерованы числами от 1 до g так, что верхняя левая точка (0, s) имеет номер 1, верхняя правая точка (s, s) – номер 2, а остальные точки – номера от 3 до g (в произвольном порядке). Красные точки пронумерованы числами от 1 до r так, что нижняя левая точка (0, 0) имеет номер 1, нижняя правая точка (s, 0) – номер 2, а остальные точки – номера от 3 до r (в произвольном порядке).



На рисунке показан пример игры, где зеленые точки соединены в одну компоненту, а красные точки – в другую.

Легко видеть, что никакие три точки на рисунке не лежат на одной прямой, и никакие два отрезка не пересекаются, кроме как по концам.
Задание
Напишите программу, которая по заданным координатам g зеленых точек и координатам r красных точек находит способ, как нарисовать (g – 1) зеленых отрезков и (r – 1) красных отрезков таким образом, чтобы все зеленые точки принадлежали одной компоненте, а все красные точки – другой, и никакие два отрезка не пересекались.

Ограничения
3≤g≤50000,g – количество зеленых точек 
3≤r≤50000
0<s≤200000000,r – количество красных точек

Входные данные
На вход Вашей программы поступают данные в следующем формате:

СТРОКА 1: Содержит целое число g.

СЛЕДУЮЩИЕ g
СТРОК: Каждая строка содержит два целых числа – координаты xi и yi каждой из g зеленых точек, начиная с точки с номером 1 и заканчивая точкой с номером g. Эти два числа разделены пробелами.

СТРОКА g + 2: Содержит целое число r.

СЛЕДУЮЩИЕ r СТРОК: Каждая строка содержит два целых числа – координаты xi и yi каждой из r красных точек, начиная с точки с номером 1 и заканчивая точкой с номером r. Эти два числа разделены пробелами.

Выходные данные
Ваша программа должна вывести (g – 1) + (r – 1) строк, каждая из которых описывает один отрезок, соединяющий две точки.

Каждая строка должна содержать два целых числа и один символ, разделенные пробелом. Числа представляют собой номера точек, соединенных этим отрезком. Если точки зеленые, то последним символом в строке должен быть g, если точки красные, то последним символом в строке должен быть r.

Ни порядок, в котором выводятся отрезки, ни порядок точек в строке не имеют значения.

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

Два неориентированных графа G и H называются изоморфными , если:

• они имеют одинаковое количество вершин;
• существует такое однозначное соответствие между их вершинами, что любые две различные вершины графа G соединены ребром тогда и только тогда, когда соединены ребром соответствующие вершины графа H.

Например, следующие два графа изоморфны, хотя выглядят по-разному:


 

Возможным однозначным соответствием, показывающим, что эти два графа изоморфны, является {a-1, b-6, c-8, d-3, g-5, h-2, i-4, j-7}, хотя существуют и другие подобные соответствия.

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

Говорят, что граф G содержит другой граф H , если существует хотя бы один подграф H ’ графа G , который изоморфен H . Следующий рисунок показывает граф G , который содержит граф H .



ЗАДАНИЕ

По двум заданным неориентированным графам G и H постройте подграф G’ графа G такой, что:

количество вершин в графах G и G’ одинаково;
H не содержится в G’ .
Естественно, может быть много подграфов графа G’ с перечисленными свойствами. Постройте подграф с как можно большим количеством ребер.

БАЗОВЫЙ АЛГОРИТМ

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

ОГРАНИЧЕНИЯ

3 ≤ m ≤ 4    m – количество вершин в H.
3 ≤ n ≤ 1000    n – количество вершин в G .

ВВОД

Вы получите 10 тестов каждый со следующими данными:
 

Пример ввода

ОПИСАНИЕ

3 5 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0

СТРОКА 1: Содержит два целых числа, разделенных пробелом, соответственно m и n. СЛЕДУЮЩИЕ m СТРОК: Каждая строка содержит m целых чисел, разделенных пробелами, и представляет одну вершину из H в порядке 1, ..., m . i -ый элемент j -ой строки в этой секции равняется 1, если вершины i и j соединены ребром в H , и равняется 0 в противном случае. СЛЕДУЮЩИЕ n СТРОК : Каждая строка содержит n целых чисел, разделенных пробелами, и представляет одну вершину из G в порядке 1, ..., n . i -ый элемент j -ой строки в этой секции равняется 1, если вершины i и j соединены ребром в G , и равняется 0 в противном случае.

 

Заметьте, что за исключением строки 1, приведенные входные данные представляют собой матрицы смежности графов H и G .

ВЫВОД

Вы должны создать 10 выводов по одному на каждый входной. Каждый тест должен содержать следующие данные:

Пример вывода

ОПИСАНИЕ

#FILE forbidden K 5 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

СТРОКА 1: Заголовок файла. Заголовок файла должен содержать #FILE forbidden K где K – это число между 1 и 10, которое соответствует решенному входному файлу. СТРОКА 2: Содержит одно целое число : n . СЛЕДУЮЩИЕ n СТРОК : Каждая строка содержит n целых чисел, разделенных пробелом, и представляет одну вершину из G’ в порядке 1, ..., n . i -ый элемент j -ой строки в этой секции равняется 1, если вершины i и j соединены ребром в G’ , и равняется 0 в противном случае.

Заметьте, что за исключением строк 1 и 2, приведенные входные данные представляют собой матрицу смежности графа G’. Обратите внимание, что есть много вариантов ответа, и приведенный вариант является корректным, но не оптимальным.

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

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

Команда	Обозначение	Действия робота
Перемещение	(X)	Переместиться вперед на X километров, прокладывая за собой оросительный канал
Поворот налево	L	Повернуть налево на 90o
Поворот направо	R	Повернуть направо на 90o

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

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

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

Входные данные
Входные данные содержат команды поворота исходной программы в том порядке, в котором они в ней следовали. Каждая команда представляет собой символ «L» либо «R», команды друг от друга не отделяются. Количество команд не превышает 30 000.

Выходные данные
Выведите  любую корректную программу, последовательность команд поворота в которой совпадает с последовательностью, заданной во входных данных. Параметр X каждой команды перемещения должен быть положительным целым числом и не должен превышать 10⁹. Все команды выведите в одной строке и друг от друга не отделяйте.

Одночлен - это выражение, состоящее из однобуквенных переменных с операциями умножения и возведения в целочисленную степень. Именами переменных являются малые латинские буквы. Умножение обозначается символом '*' (ASCII 42), возведение в степень - символом '^' (ASCII 94). Показатель степени состоит из одной десятичной цифры от 1 до 9. Примеры одночленов: t, a*b*c^2, y*d^1*y^9.

Требуется по данным N + M одночленам построить дробь, равную произведению первых N одночленов, делённому на произведение оставшихся M одночленов. При этом:

1) Числитель и знаменатель дроби должны быть одночленами.

2) Переменная не должна встречаться в дроби более одного раза (т. е. дробь необходимо сократить).

3) Степени переменных должны быть целыми числами большими или равными 2.

4) В числителе и знаменателе переменные должны быть отсортированы по алфавиту.

Входные данные
В первой строке входного файла содержатся числа N и M (1 <= N, M <= 999), разделённые пробелами.

Следующие N + M строк содержат по одному одночлену каждая. Длина каждой строки не превосходит 100 символов.

Выходные данные
В выходном файле должны быть две строки, содержащие соответственно числитель и знаменатель результата. Если после сокращения в числителе и/или в знаменателе не остаётся ни одной переменной, вместо одночлена следует вывести число 1.

Последовательность чисел монотонно убывающая если для любого i элемента (кроме последнего )выполняется A_i > A_i+1. Последовательность чисел монотонно возрастающая если для любого i элемента (кроме последнего )выполняется A_i < A_i+1. Последовательность монотонная если она или монотонно убывающая или монотонно возрастающая. Дана последовательность A_i из n чисел. Каждый элемент последовательности можно увеличивать или уменьшать. Требуется изменить последовательность так что бы в ней содержалось K монотонных непересекающихся последовательностей. (один элемент тоже последовательность). Т.к. преобразований бесконечно много то нужно найти такое преобразование чтобы сумма разностей по модулю конечного значения A_i и начального значения A_i была минимальна.

Входные данные
В первой строчке n,k n- количество элементов в последовательности, k сколько должно быть монотонных последовательностей. Во второй строчке n чисел через пробел - сама последовательность(каждое число по модулю меньше 20,000,000)

Выходные данные
Одно число, ответ на задачу.

На съезд лауреатов конкурсов Киноакадемии приглашены \(n\) кинозвёзд, которые очень трепетно относятся к различным слухам о себе. Необходимо, чтобы среди \(\frac{n(n-1)}{2}\) возможных пар кинозвёзд оказалось ровно \(a\) пар, в которых обе кинозвезды ни в какой момент времени не будут присутствовать в зале съезда вместе, и ровно \(b\) пар, в которых одна из кинозвёзд будет присутствовать в зале только вместе с другой: войдет в зал позже нее, а выйдет раньше.

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

Требуется для каждого из \(q\) заданных съездов по \(n\), \(a\) и \(b\) определить подходящую последовательность входа и выхода кинозвёзд в зал.

Формат входных данных
Первая строка входного файла содержит целое число \(q\) — количество съездов. Каждая из последующих \(q\) строк содержит описание съезда: три целых числа \(n\), \(a\) и \(b\).

Формат выходных данных
Выходной файл должен содержать \(q\) строк — по одной на каждый съезд. Каждая строка должна содержать число \(n\), после которого следуют \(2n\) целых чисел, описывающих порядок входа и выхода кинозвёзд в зал. Каждое число в диапазоне от \(1\) до \(n\) должно встречаться дважды: в первый раз число \(i\) обозначает вход \(i\)-й кинозвёзды в зал, во второй раз — её выход.

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

Если решение для конкретного съезда вами не найдено, в соответствующей строке необходимо вывести единственное число \(0\).

Требуется решить задачу для 7 тестов, которые находятся на вашем компьютере в каталоге <<c:work6-tests>> в файлах с именами 01, 02, 03, 04, 05, 06 и 07. На проверку требуется сдавать только файлы с ответами. Сдавать программу не требуется.

За каждый тест, ответ на который отправляется в проверяющую систему, начисляется \(k\) баллов, где \(k\) — число съездов, для которых было найдено правильное решение.

Если присланный файл не соответствует требованиям к формату выходных данных, то он не будет принят на окончательную проверку с сообщением <<PE 1>>.

В течение тура можно не более 10 раз по каждому тесту запросить информацию о результатах оценивания ответа. Запрос по каждому тесту можно делать не чаще одного раза в 5 минут. В качестве результата проверки сообщается количество полученных баллов и комментарий проверяющей программы, который содержит информацию о правильности решений для съездов в порядке их перечисления во входном файле в следующем формате:

• <<+>> — решение правильное, за него начислен 1 балл;

• <<->> — решение неправильное;

• <<0>> — присланный файл содержит 0 для этого съезда.

В приведённом в примере ответе на тест, решение для второго съезда не найдено, а решение для четвертого теста неправильное. Если бы это был один из тестов жюри, такой ответ был бы оценен в 2 балла из 4.

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

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

Руководство университета заинтересовалось разнообразием питания студентов, покупающих продукты в автоматах по ходу движения. Для каждого автомата \(A_{i,j}\) планируется найти кратчайший путь из общежития в учебный корпус, проходящий через этот автомат и содержащий как можно больше автоматов, торгующих тем же самым продуктом, что и автомат \(A_{i,j}\). Количество таких автоматов на этом пути называется избыточностью автомата \(A_{i,j}\). При этом автомат \(A_{1,1}\) находится в общежитии, а автомат \(A_{n,n}\) — в учебном корпусе.

Требуется написать программу, которая по информации о продуктах, продаваемых автоматами, для каждого из чисел в диапазоне от \(1\) до \(2n - 1\) определяет число автоматов с таким значением избыточности.

Формат входных данных
Первая строка содержит целое число \(n\) (\(2 \leqslant n \leqslant 1500\)). Следующие \(n\) строк содержат по \(n\) чисел в каждой. В \(i\)-й из этих строк \(j\)-е число соответствует номеру продукта, продающегося в автомате \(A_{i,j}\). Номера продуктов находятся в диапазоне от \(1\) до \(n^2\).

Формат выходных данных
Строка должна содержать \((2n-1)\) целых чисел — количество автоматов с избыточностями \(1, 2, \ldots, 2n - 1\) соответственно.

Вадим работает в ЖКХ и сегодня он крайне озабочен вопросов сосулек. А именно он наблюдает за домом по адресу — проспект Программистов, дом 404. В доме \(n\) этажей, на каждом этаже по \(m\) окон, включая первый. Окна на каждом этаже пронумерованы слева направо от \(1\) до \(m\). \(i\)-e окно \(j\)-го этажа находится ровно под \(i\)-м окном \(j + 1\)-го этажа. Под некоторыми окнами свисают сосульки.

Вадим руководит установкой на дом козырька, который будет установлен ниже первого этажа и проходить под \(d\) окнами. То есть, если начало козырька находится под окном с номером \(i\), то он проходит под всеми окнами с номерами от \(i\) до \(i + d - 1\). Вадим хочет выбрать такую позицию для козырька, чтобы над ним находилось наименьшее возможное количество сосулек и из всех подходящих вариантов выбрать такой, что начало козырька будет находиться как можно левее.

Помогите Вадиму выбрать нужное окно.

Формат входных данных
В первой строке содержатся числа \(n\), \(m\), \(d\), \(k\) — количество этажей, количество окон на каждом этаже, длина козырька и количество окон, под которыми есть сосульки, соответственно (\(1 \le n, m \le 100\),\(1 \le d \le m\), \(0 \le k \le n \cdot m\)).

В следующих \(k\) строках заданы тройки чисел \(x\), \(y\), \(z\) — номер этажа, номер окна на этаже и количество сосулек под ним (\(1 \le x \le n\), \(1 \le y \le m\), \(1 \le z \le 10\)).

Гарантируется, что каждая пара \(x\), \(y\) встречается не более одного раза.

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

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

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

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

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

Для некоторого числа \(m\) назовём \(m\)-разбиением массива такое его разбиение на непересекающиеся отрезки, что на каждом из этих отрезков медиана больше либо равна \(m\). Вам дан массив \(a\) длины \(n\) и \(q\) запросов двух видов:

1. присвоить элементу с индексом \(i\) значение \(x\);

2. найти наибольшее число \(k\) такое, что для подотрезка массива с индексами от \(l\) до \(r\) существует \(m\)-разбиение на \(k\) отрезков.

Формат входных данных
В первой строке дается число \(n\) (\(1 \le n \le 2 \cdot 10^5\)) - размер массива. В следующей строке вводятся \(n\) чисел \(a_{i}\) (\(1 \le a_{i} \le 10^9\)) - элементы массива, на следующей строке вводится число \(q\) (\(1 \le q \le 2 \cdot 10^5\)) - количество запросов. В следующих \(q\) строках даются запросы, каждый в одном из следующих форматов:

• \(1\) \(i\) \(x\) —  запрос 1 типа (\(1 \le i \le n, 1 \le x \le 10^9\));

• \(2\) \(m\) \(l\) \(r\) —  запрос 2 типа (\(1 \le m \le 10^9, 1 \le l \le r \le n\)).

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

В задаче присутствуют 6 групп:

1. \(n \le 5, q \le 5\), такие решения будут набирать не менее 10% баллов

2. \(n \le 100, q \le 100\), такие решения будут набирать не менее 20% баллов

3. \(n \le 10000, q \le 10000\), такие решения будут набирать не менее 30% баллов

4. \(m\) - одно и тоже для всех запросов, такие решения будут набирать не менее 25% баллов

5. нет запросов изменения, такие решения будут набирать не менее 35% баллов

6. Ограничения, как и в задаче

Федок очень хочет купить себе комплексный обед в столовой, но сделать это не так просто. В столовой работает всего одна касса, и то очень медленно. На данный момент в очереди находится \(n\) \((2 \leq n \leq 100\,000)\) людей, а сам Федок находится на \(k-\)ой \((1 \leq k \leq n)\) позиции в ней. И вот, чтобы занять себя в этой очереди, Федок стал обдумывать коварный план как побыстрее оплатить комплексный обед и начать есть.

В чем состоит коварный план? Федок хочет крикнуть, что открылась новая касса. Тогда, по его мнению, многие уйдут из очереди в поисках этой кассы, а он приблизится к заветной еде. Но вот в чем проблема: не все люди так нетерпеливы как наш герой. Проще говоря, у каждого человека есть свой параметр \(P_i\) — терпеливость. Если человек стоит на позиции \(x\) и его терпеливость равна \(y\), то он уйдет искать новую кассу только в том случае, если \(y < x\)

Казалось бы, эта задача трудна, но и Федок не глуп. Он своим метким взором определил терпеливости всех людей, стоящих в очереди кроме него. Увы, так как людей очень много, в его голове все перепуталось, и некоторые числа поменялись местами. Таким образом наш герой получил некоторую перестановку множества терпеливости всех людей в очереди \(P_1, P_2, \ldots, P_{n-1}\)

Федок не знает точно, кто насколько терпелив и боится, что не сдвинется в очереди после реализации своей задумки. Поэтому он просит вас помочь ему узнать, какую минимальную и максимальную позицию от начала очереди он может занимать после того как крикнет: <<Свободная касса!>>

Формат входных данных
В первой строке входных данных находится число людей в очереди \(n\) (\(2 \leq n \leq 100\,000\))

Во второй строке находится число \(k\) (\(1 \leq k \leq n\)) — текущая позиция Федка в очереди

В следующей строке содержатся \(n-1\) число — перестановка множества терпеливостей людей в очереди \((0 \leq P_i \leq n)\)

Формат выходных данных
В первой строке выведите минимальное место, которое может стать у Федка после применения его плана

Во второй строке выведите максимальное место, которое может стать у Федка после применения его плана

• Решения, работающие для \(n \leq 10\) будут набирать не менее 5 баллов

• Решения, работающие для \(n \leq 1000\) будут набирать не менее 10 баллов

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

Алексей стоит на второй позиции. Перед ним один человек.

Если его терпеливость будет равна нулю, то он уйдет, и Федок станет первым

Если же его терпеливость равна трем, то он не уйдет, и Федок останется второй

Миша сидел на занятиях математики в Высшей школе экономики и решал следующую задачу: дано \(n\) целых чисел и нужно расставить между ними знаки \(+\) и \(\times\) так, чтобы результат полученного арифметического выражения был нечётным (например, между числами \(5\), \(7\), \(2\), можно расставить арифметические знаки следующим образом: \(5 \times 7 + 2 = 37\)). Так как примеры становились все больше и больше, а Миша срочно убегает в гости, от вас требуется написать программу решающую данную задачу.

Формат входных данных
В первой строке содержится единственное число \(n\) (\(2 \leq n \leq 10^5\)). Во второй строке содержится \(n\) целых чисел \(a_i\), разделённых пробелами (\(-10^9 \leq a_i \leq 10^9\)). Гарантируется, что решение существует.

Формат выходных данных
В одной строке выведите \(n - 1\) символ \(+\) или \(\times\), в результате применения которых получается нечётный результат. (Для вывода используйте соответственно знаки <<+>> (ASCII код—43) и <<x>> (ASCII код—120), без кавычек).

 

Саша считает красивыми числа, десятичная запись которых не содержит других цифр, кроме 0 и k (1 ≤ k ≤ 9). Например, если k = 2, то такими числами будут 2, 20, 22, 2002 и т.п. Остальные числа Саше не нравятся, поэтому он представляет их в виде суммы красивых чисел. Например, если k = 3, то число 69 можно представить так: 69 = 33 + 30 + 3 + 3.
Однако, не любое натуральное число можно разложить в сумму красивых целых чисел. Например, при k = 5 число 6 нельзя представить в таком виде. Но если использовать красивые десятичные дроби, то это можно сделать: 6 = 5.5 + 0.5.
Недавно Саша изучил периодические десятичные дроби и начал использовать и их в качестве слагаемых. Например, если k = 3, то число 43 можно разложить так: 43 = 33.(3) + 3.(3) + 3 + 3.(3).
Оказывается, любое натуральное число можно представить в виде суммы положительных красивых чисел. Но такое разложение не единственно — например, число 69 можно также представить и как 69 = 33 + 33 + 3. Сашу заинтересовало, какое минимальное количество слагаемых требуется для представления числа n в виде суммы красивых чисел.
Требуется написать программу, которая для заданных чисел n и k находит разложение числа n в сумму положительных красивых чисел с минимальным количеством слагаемых. Формат входных данных На вход программы поступают два натуральных числа n и k (1 ≤ n ≤ 10⁹; 1≤ k ≤ 9).

Формат входных данных
На вход программы поступают два натуральных числа n и k (1 ≤ n ≤ 10⁹; 1≤ k ≤ 9).

Формат выходных данных
Выведите разложение числа n в сумму положительных чисел, содержащих только цифры 0 и k, количество слагаемых в котором минимально. Разложение должно быть представлено в виде: Слагаемые a₁, a₂, ..., a_m должны быть выведены без ведущих нулей, без лишних нулей в конце дробной части. Запись каждого слагаемого должна быть такой, что длины периода и предпериода дробной части имеют минимально возможную длину. Например, неправильно выведены числа: 07.7; 2.20; 55.5(5); 0.(66); 7.(0); 7. ; .5; 0.33(03). Их следует выводить так: 7.7; 2.2; 55.(5); 0.(6); 7; 7; 0.5; 0.3(30). Предпериод и период каждого из выведенных чисел должны состоять не более чем из 100 цифр. Гарантируется, что хотя бы одно такое решение существует. Если искомых решений несколько, выведите любое. Порядок слагаемых может быть произвольным. Выходные данные не должны содержать пробелов.

Примечание
Ответ программы для первого примера: 10=10 Ответ программы для второго примера: 42=6+6+6+6+6+6+6 Ответ программы для третьего примера: 57=11+11+11+11+11+1+1 Выводить нужно именно так. Ниже содержится служебная информация в качестве ответа

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

На вас возложили ответственную задачу по управлением роботом-курьером. Карта, по которой перемещается робот, представляет из себя поле размера \(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>>) — зеленым.

В секретной лаборатории профессора Хаоса проходит эксперимент по выращиванию особо опасных бактерий. В начале первого дня эксперимента у Хаоса имеется \(a\) особо опасных бактерий.

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

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

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

Теперь профессор Хаос хочет выяснить, сколько особо опасных бактерий будет у него в контейнере после \(k\)-го дня эксперимента. Помогите ему найти ответ на этот вопрос.

Формат входных данных
В единственной строке входного файла содержится пять целых чисел \(a\), \(b\), \(c\), \(d\) и \(k\) (\(1 \le a, b \le 1000\), \(0 \le c \le 1000\), \(1 \le d \le 1000\), \(a \le d\), \(1 \le k \le 10^{18}\)).

Формат выходных данных
Выведите одно число — количество бактерий у Хаоса к концу \(k\)-го дня. Если эксперимент завершится в \(k\)-й день или ранее, выведите число 0.