Язык программирования

Темное царство представляет собой лабиринт NxM, некоторые клетки которого окружены зеркальными стенами, а остальные — пустые. Весь лабиринт также окружен зеркальной стеной. В одной из пустых клеток лабиринта поставили светофор, который испускает лучи в 4 направлениях: под 45 градусов относительно стен лабиринта. Требуется изобразить траекторию этих лучей.

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


Входные данные
В первой строке входного файла записаны два натуральных числа N и M — число строк и столбцов в лабиринте (каждое из чисел не меньше 1 и не больше 100). В следующих N строках записано ровно по M символов в каждой — карта лабиринта. Символ * (звездочка) обозначает клетку, окруженную зеркальными стенками, . (точка) — пустую клетку, символ X (заглавная латинская буква X) — клетку, в которой расположен светофор (такая клетка ровно одна).

Выходные данные
В выходной файл выведите N строк по M символов в каждой — изображение лабиринта с траекториями лучей. Здесь, как и раньше, * (звездочка) должна обозначать клетки, окруженные зеркальными стенами, . (точка) — пустые клетки, через которые лучи света не проходят, / (слеш) — клетки, через которые луч света проходит из левого нижнего угла в правый верхний (или обратно — из правого верхнего в левый нижний), \ (обратный слеш) — клетки, через которые луч проходит из левого верхнего угла в правый нижний (или обратно), а символ X (заглавная латинская буква X) — клетки, через которые лучи проходят по обеим диагоналям.

Примеры

№	Входные данные	Выходные данные
1	3 5 X.... ..... .....	XXXXX XXXXX XXXXX
2	3 3 ... ..X ...	/X\ X.X \X/

В новой модели сотового телефона разработчики предусмотрели только 5 кнопок: «стрелка вверх», «стрелка вниз», «стрелка вправо», «стрелка влево» и «Ok». Чтобы набрать номер телефона, на экран выводится виртуальная клавиатура в виде такой таблицы:
 

1	2	3
4	5	6
7	8	9
выход	0	звонок

По ячейкам этой таблицы пользователь телефона может перемещать курсор вверх, вниз, вправо или влево. Для выбора цифры необходимо нажать кнопку «Ok». После набора всех цифр пользователь должен подвинуть курсор на ячейку «звонок» и нажать «Ok». Таблица не «зациклена» (это означает, что нажатие кнопки «вправо», например, из ячейки с цифрой 6 не приведет к перемещению курсора).

При вызове экранной клавиатуры курсор находится на кнопке с надписью «выход».

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

Входные данные
Во входном файле задан номер телефона, содержащий ровно 7 цифр.

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

Примеры

№	Входные данные	Выходные данные
1	0800000	12
2	1234567	24

Дано верное равенство вида a₁+a₂+…+a_N=b₁+b₂+…b_M, где a₁,a₂,…,a_N, b₁,b₂,…,b_M – некоторые действительные (не обязательно целые) числа. Требуется «округлить» это равенство, т.е. получить новое верное равенство c₁+c₂+…+c_N=d₁+d₂+…+d_M, где c₁,c₂,…,c_N,d₁,d₂,…,d_M — целые числа, и при этом c₁ получено округлением числа a₁ до целого вверх или вниз (так, например, число 1.7 разрешается округлить как до 1, так и до 2), c₂ получено округлением a₂, …, c_N – округлением a_N, d₁ – округлением b₁, …, d_M – округлением b_M. Если какое-то из чисел в исходном равенстве было целым, оно должно остаться без изменений.

Входные данные
Во входном файле задано сначала число N, затем N чисел a₁, a₂, …, a_N, затем число M, затем числа b₁, b₂, …, b_M. Каждое число задается на отдельной строке. M и N – натуральные числа, не превышающие 1000. Остальные числа — вещественные, каждое из них по модулю не превышает 1000 и содержит не более 6 цифр после десятичной точки. При этом a₁+a₂+…+a_N=b₁+b₂+…b_M.

Выходные данные
Если «округлить» равенство можно, то в выходной файл выведите сначала числа c₁,c₂,…,c_N, а затем числа d₁,d₂,…,d_M. Все числа должны быть целыми и выведены без десятичной точки. Числа должны разделяться пробелами или переводами строки. Если решений несколько, выведите любое из них.

Если округлить исходное равенство до верного целочисленного равенства невозможно, выведите одно число 0.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 0.15 -3.000 2.7 1 -0.15	1 -3 2 0	Обратите внимание, что число –3 может округляться только в –3, в то время как 0.15 можно округлить как до 0, так и до 1, 2.7 – до 2 или до 3, –0.15 – до –1 или до 0. Приведенное решение не является единственным: так же верным является, например, такое округление: 1+(–3)+2=0
2	2 1.7 2.5 3 1 2.000 1.20	2 2 1 2 1	Приведенное решение 1+3=1+2+1 не является единственным. Верными ответами также являются 2+2=1+2+1 и 2+3=1+2+2.
3	1 0.5 1 0.5	0 0	Здесь верными являются как ответ 1=1, так и 0=0.

Напишите программу, которая по изображению поля для игры в «Крестики-нолики» определит, могла ли такая ситуация возникнуть в результате игры с соблюдением всех правил.

Напомним, что игра в «Крестики-нолики» ведется на поле 3×3. Два игрока ходят по очереди. Первый ставит крестик, а второй – нолик. Ставить крестик и нолик разрешается в любую еще не занятую клетку поля. Когда один из игроков поставит три своих знака в одной горизонтали, вертикали или диагонали, или когда все клетки поля окажутся заняты, игра заканчивается.

Входные данные
Вводится три строки по три числа в каждой, описывающих игровое поле. Число 0 обозначает пустую клетку, 1 – крестик, 2 – нолик. Числа в строке разделяются пробелами.

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

Примеры

№	Входные данные	Выходные данные
1	1 1 1 1 1 1 1 1 1	NO
2	2 1 1 1 1 2 2 2 1	YES
3	1 1 1 2 0 2 0 0 0	YES
4	0 0 0 0 1 0 0 0 0	YES
5	1 1 1 2 2 2 0 0 0	NO

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

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

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

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

Примеры

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

На клетчатой бумаге нарисована карта острова (клетки острова закрашены). При этом остров является клетчато-выпуклой фигурой, то есть каждая горизонтальная или вертикальная линия на карте либо не пересекает остров, либо пересекает его по отрезку (линия пересечения не содержит разрывов). Также остров является связной фигурой, то есть любые две клетки острова соединены путём, каждые две соседние клетки которого имеют общую сторону.

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


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

Выходные данные
Программа получает на вход два числа N и M, записанные в отдельных строках, — количество строк и столбцов карты острова (3 ≤ N ≤ 100, 3 ≤ M ≤ 100). Далее записана карта острова — N строк, каждая содержащая M символов. Каждый символ карты может быть либо символом «.», что означает клетку, не принадлежащую острову, либо символом «#», что означает клетку острова. При этом остров не касается края карты.

Введём на карте систему координат. Первая координата является номером строки, строки нумеруются сверху вниз числами от 1 до N. Вторая координата — номер столбца, столбцы нумеруются слева направо числами от 1 до M.

Входные данные
Программа должна вывести координаты клеток карты в порядке их облёта самолётом. Каждая строка вывода должна содержать два числа x и y — координаты самолёта, записанные через пробел (1 ≤ x ≤ N, 1 ≤ y ≤ M). Самолёт должен побывать в каждой соседней с островом клетке ровно один раз. Каждые две клетки, идущие подряд в выводе, должны иметь общую сторону. Можно вывести любой возможный маршрут облёта острова.

Примеры

№	Входные данные	Выходные данные
1	6 7 ....... ....... ....... .###... .###... .......	3 1 3 2 3 3 3 4 3 5 4 5 5 5 6 5 6 4 6 3 6 2 6 1 5 1 4 1

Телефонные номера в адресной книге мобильного телефона имеют один из следующих форматов:

+7<код><номер>

8<код><номер>

<номер>

где <номер> — это семь цифр, а <код> — это три цифры или три цифры в круглых скобках. Если код не указан, то считается, что он равен 495. Кроме того, в записи телефонного номера может стоять знак “-” между любыми двумя цифрами (см. пример).

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

Два телефонных номера совпадают, если у них равны коды и равны номера. Например, +7(916)0123456 и 89160123456 — это один и тот же номер.

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

Гарантируется, что каждая из записей соответствует одному из трех приведенных в условии форматов.

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

Примеры

№	Входные данные	Выходные данные
1	8(495)430-23-97 +7-4-9-5-43-023-97 4-3-0-2-3-9-7 8-495-430	YES YES NO

Миша готовится к ЕГЭ по информатике. Сейчас он изучает задачу A4, в которой описывается работа с масками файлов:

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

Символ «?» (вопросительный знак) означает ровно один произвольный символ.

Символ «*» (звёздочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность.

Поскольку открытого банка задач для ЕГЭ по информатике не существует, Мише приходится тренироваться самостоятельно. Напишите программу, которая для каждого имени файла определит, подходит ли оно под заданную маску, чтобы Миша мог сверить свои ответы. Гарантируется, что в маске файла присутствует не более одного символа «*».

Входные данные
В первой строке содержится маска файла. В следующих 5 строках содержатся имена файлов по одному в строке. Имена файлов состоят из маленьких латинских букв, цифр и символа «.» (точка), в маске также могут содержаться символы «?» и «*» (символ «*» — не более одного раза). Длина каждой строки не превосходит 20 символов.

Выходные данные
Для каждого имени файла выведите слово «YES» если оно удовлетворяет маске и «NO» иначе. Выводить слова следует большими латинскими буквами без кавычек, каждое в новой строке.

Примеры

№	Входные данные	Выходные данные
1	?or*.d?? fort.doc ford.doc lord2.doc orsk.dat port	YES YES YES NO NO

Про три числа (обозначенных a, b, c) известны все результаты сравнения их друг с другом. Требуется расположить эти числа в порядке возрастания.

Входные данные
Вводятся три строки. В первой записан результат сравнения между собой чисел a и b в следующем формате. Первый символ — всегда a, третий символ — b (соответствующие маленькие латинские буквы), а между ними записан один из символов >, < или =. Во второй строке в таком же формате записан результат сравнения a и с (первый символ всегда a, третий — c), а в третьей строке — результат сравнения b и c (первый символ всегда b, третий — c). Гарантируется, что входные данные не противоречивы.

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

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

Примеры

№	Входные данные	Выходные данные
1	a>b a>c b>c	cba
2	a=b a>c b>c	cab cba

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

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

Например, для K=2 последовательности получатся такими:

№	Последовательность	Как ее читать (слова в описании соответствуют числам текущей последовательности слева направо, и описывают предыдущую последовательность)
1	2	Исходная последовательность
2	1 2	Одна «двойка»
3	1 1 1 2	Одна «единица», одна «двойка»
4	3 1 1 2	Три «единицы», одна «двойка»
5	1 3 2 1 1 2	Одна «тройка», две «единицы», одна «двойка»
6	1 1 1 3 1 2 2 1 1 2	Одна «единица», одна «тройка», одна «двойка», две «единицы», одна «двойка»

Напишите программу, которая по исходному числу K напечатает N-ую получающуюся последовательность.

Входные данные
Вводится число K (1 ≤ K ≤ 9) и число N (1 ≤ N ≤ 15).

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

Примеры

№	Входные данные	Выходные данные
1	2 6	1 1 1 3 1 2 2 1 1 2
2	2 1	2
3	1 3	2 1

На контрольной работе N учеников сидят в ряд. Для каждого ученика известно, какую оценку он получил бы, если бы писал эту контрольную самостоятельно (оценка — это число от 2 до 5). Однако ученики могут писать контрольную не только самостоятельно, но и списывать у своего соседа, но только если сосед пишет контрольную самостоятельно. В этом случае списывающий получит такую же оценку, какую получит тот, у кого он списал.

А именно (правила применяются строго в указанном порядке):

• Школьники, которые знают материал на 5, будут писать контрольную самостоятельно.
• Школьник, который знает материал на 4, если он сидит рядом с тем, кто знает на 5, будет списывать у него, а в противном случае будет писать самостоятельно.
• Школьник, который знает на 3, если он сидит рядом с тем, кто знает на 5, будет списывать у него. Если среди его соседей знающего на 5 нет, но есть тот, кто знает на 4, и при этом пишет самостоятельно, то троечник будет списывать у него. В противном случае будет писать самостоятельно.
• Аналогично школьник, знающий на 2 — из соседей, которые пишут самостоятельно, выберет того, кто знает лучше, и спишет у него. А если таких нет (или оба его соседа также знают на 2), то будет писать самостоятельно.

Определите, кто какую оценку в итоге получит.

Входные данные
Вводится число N (1<=N<=10) - количество учеников, и далее последовательность из N чисел, описывающая, кто на какую оценку может написать контрольную, если будет писать самостоятельно.

Выходные данные
Выведите N чисел - оценки, которые получат ученики за контрольную.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 5 2 3 4 5	5 5 3 5 5	Первый и пятый ученики будут писать самостоятельно. Второй спишет у первого, а четвертый — у пятого (в итоге также получат пятерки). Третьему не у кого списывать, так как его соседи будут писать работу не самостоятельно.
2	6 2 2 3 2 2 4	2 3 3 3 4 4	Второй и четвертый спишут у третьего, пятый — у шестого.

Пете нужно оклеить обоями стену размером N метров в высоту и M метров в ширину. Для поклейки используются обои, которые продаются рулонами. Каждый рулон имеет ширину 1 метр и длину K метров. Обои клеятся на стену вертикальными полосами (сверху вниз). При этом Петя хочет так поклеить обои, чтобы горизонтальных стыков разных кусков не было (то есть один цельный кусок клеится от потолка до пола). От рулона можно отрезать куски нужного размера (иногда при этом может оставаться кусок, меньшего размера, который поэтому не может быть поклеен, этот кусок идет в отходы).

По данным числам N, M и K определите наименьшее количество рулонов, которое нужно купить Пете, чтобы оклеить всю стену.

Формат входных данных
Вводятся натуральные числа N, M и K (1 ≤ N ≤ 100, 1 ≤ M ≤ 100, N ≤K ≤100).

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

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

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

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

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

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

Гарантируется, что входные данные будут таковы, что количество символов, которое нужно будет вывести в одной строке, не превысит 79.

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

Примеры

№	Входные данные	Выходные данные
1	2 3 2 3 3	...#......#.... ..###....###... ...#....#####.. ..###.....#.... .#####...###... ...#....#####.. ..###..#######. .#####....#.... #######..###... ........#####.. .......#######. ......#########
2	3 1 1 2 1 3 2	#.#...#... ..#..###.. .###..#... .....###.. ....#####. ......#... .....###.. ....#####. ...#######

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

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

Выходные данные
Выведите два числа — размеры стола. Если возможно несколько ответов, выведите любой из них (но только один).

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

Примеры

№	Входные данные	Выходные данные
1	10 2 2 10	20 2 2 20 4 10 10 4
2	5 7 3 2	9 5 5 9

В школе продолжительность каждого урока 45 минут, а перемены между уроками – всего 5 минут. Первый урок начинается ровно в 8 часов утра. Напишите программу, отвечающую на вопрос «во сколько в этой школе заканчивается K-ый урок?»

Формат входных данных
Вводится одно натуральное число K, не превышающее 15.

Формат выходных данных
Выведите время окончания K-ого урока: сначала часы, потом минуты, разделяя их пробелом.

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

Входные данные
Вводится сначала K — вес предмета, который положили на левую чашу (1≤K≤50). Далее записано общее количество гирек N (1≤N≤10). Далее записано N различных натуральных чисел, не превышающих 50, — веса гирек.

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

Примеры

№	Входные данные	Выходные данные
1	5 2 3 5	0 5
2	5 3 6 3 4	4 3 6
3	5 1 2	-1

В новой программе OpenCalculator появилась новая возможность – можно настроить, какие кнопки отображаются, а какие – нет. Если кнопка не отображается на экране, то ввести соответствующую цифру с клавиатуры или копированием из другой программы нельзя. Петя настроил калькулятор так, что он отображает только кнопки с цифрами x, y, z. Напишите программу, определяющую, сможет ли Петя ввести число N, а если нет, то какое минимальное количество кнопок надо дополнительно отобразить на экране для его ввода.

Входные данные
Сначала вводятся три различных числа из диапазона от 0 до 9: x, y и z (числа разделяются пробелами). Далее вводится целое неотрицательное число N, которое Петя хочет ввести в калькулятор. Число N не превышает 10000.

Выходные данные
Выведите, какое минимальное количество кнопок должно быть добавлено для того, чтобы можно было ввести число N (если число может быть введено с помощью уже имеющихся кнопок, выведите 0)
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	1 2 3 1123	0	Число может быть введено имеющимися кнопками.
2	1 2 3 1001	1	Нужно добавить кнопку 0.
3	5 7 3 123	2	Нужно добавить кнопки 1 и 2.

Секретное агентство «Super-Secret-no» решило для шифрования переписки своих сотрудников использовать «метод бутерброда». Сначала буквы слова нумеруются в таком порядке: первая буква получает номер 1, последняя буква - номер 2, вторая – номер 3, предпоследняя – номер 4, потом третья … и так для всех букв (см. рисунок). Затем все буквы записываются в шифр в порядке своих номеров. В конец зашифрованного слова добавляется знак «диез» (#), который  нельзя использовать в сообщениях.

Например, слово «sandwich» зашифруется в «shacnidw#».



К сожалению, программист «Super-Secret-no», написал только программу шифрования и уволился. И теперь агенты не могут понять, что же они написали друг другу. Помогите им.

Входные данные
Вводится слово, зашифрованное методом бутерброда. Длина слова не превышает 20 букв.

Выходные данные
Выведите расшифрованное слово.

Примеры

№	Входные данные	Выходные данные
1	Aabrrbaacda#	Abracadabra

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

Автомат представляет собой последовательность из блоков двух типов: максимизаторов и минимизаторов . На каждом блоке написано некоторое натуральное число x . Максимизатор принимает на вход натуральное число a и подает на выход число max ( x , a ) . Минимизатор принимает на вход натуральное число a и подает на выход число min ( x , a ) .

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

Изначально в автомате нет ни одного блока, и он просто возвращает число, которое принимает.

Андрюша последовательно выполняет действия с автоматом. Действия бывают трех типов:

1. Добавить в конец последовательности блоков автомата максимизатор, на котором написано число x .
2. Добавить в конец последовательности блоков автомата минимизатор, на котором написано число x .
3. Подать на вход автомату число x . В этом случае Андрюша хочет узнать, что автомат вернет на выход.

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

Входные данные
Первая строка входных данных содержит единственное целое число n ( 1 ≤ n ≤ 4·10⁵ ) — суммарное количество действий Андрюши.

В каждой из следующих n строк содержится по два целых числа t и x ( 1 ≤ t ≤ 3 , 1 ≤ x ≤ 10⁹ ), где t — это тип очередного действия. Если t = 1 , то Андрюша хочет добавить к автомату максимизатор, на котором написано число x . Если t = 2 , то Андрюша хочет добавить к автомату минимизатор, на котором написано число x . Если t = 3 , то Андрюша хочет подать на вход автомату число x и узнать, что получится на выходе.

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

Примеры

№	Входные данные	Выходные данные
1	7 3 5 1 5 3 2 3 7 2 7 3 8 3 6	5 5 7 7 6

У Карлсона дома есть набор из n банок с конфетами. Банки пронумерованы от 1 до n , в i -й из них лежит a i конфет. Карлсон считает набор банок симпатичным , если в этом наборе нет трех банок с разным числом конфет.

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

Входные данные
Первая строка входных данных содержит натуральное число n ( 1 ≤ n ≤ 10⁵ ) — количество банок в наборе Карлсона.

Вторая строка входных данных содержит n целых чисел a_i ( 0 ≤ a_i ≤ 10⁹ ) — число конфет в банках. Соседние числа отделены друг от друга одним пробелом.

Выходные данные
Выведите одно число — минимальное общее количество конфет, которое придется добавить, чтобы Карлсон считал набор банок симпатичным.

Примечание
В первом тесте из примера Карлсон может добавить в первую банку две конфеты, а во вторую банку — одну конфету. Тогда в первой и четвертой банках будет лежать по 7 конфет, а во второй и третьей — по 2 конфеты.

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

Примеры

№	Входные данные	Выходные данные
1	4 5 1 2 7	3
2	3 1 1 1	0