Информатика

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

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

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

Помогите Андрею найти первое следующее в алфавитном порядке слово, состоящее из тех же букв, что и заданное слово, и состоящее ровно из \(k\) букв. Гарантируется, что такое слово существует.

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

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

В третьей строке задано целое число \(k\) (\(1 \leq k \leq 100\,000\)) — количество букв в искомом слове.

Формат выходных данных
Выведите искомое слово, состоящее из \(k\) букв, входящих в первое слово.

В первом тестовом примере требуемое слово должно состоять из букв a, b и c. Следующим после abc в алфавитном порядке будет слово abca, но оно состоит из 4 букв, а не из 3. Следующим после abc в алфавитном порядке состоящим из букв a, b и c и имеющим длину 3 будет слово aca.

В данной задаче \(50\) тестов, помимо тестов из условия. 

Не менее чем в 15 тестах первое слово будет состоять только из букв abc, причем каждая из трех букв будет встречаться. 

Решения, работающие при \(1 \leq n, k \leq 3\) будут набирать не менее \(10\) баллов.

Решения, работающие при \(1 \leq n, k \leq 10\) будут набирать не менее \(30\) баллов.

Решения, работающие при \(1 \leq n, k \leq 5\,000\) будут набирать не менее \(60\) баллов.

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

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

Формат входных данных
Во входных данных записано единственное целое число \(n\) — максимально возможная длина шеи жирафа (\(1 \leq n \leq 10^9\)).

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

Замечание

В примере из условия необходимо подобрать такой набор из минимального числа подушек, чтобы используя данные подушки удавалось сложить стопку любой целочисленной толщины от \(1\) до \(9\) см. Таким набором является набор из подушек толщиной \(1\), \(2\), \(3\), \(3\) см. Действительно, стопку толщины \(1\), \(2\), \(3\) см можно сложить из одной подушки. Оставшиеся числа получены так: \(4=1+3\), \(5=2+3\), \(6=3+3\), \(7=1+3+3\), \(8=2+3+3\), \(9=1+2+3+3\). Возможны и другие варианты ответа с тем же количеством подушек и их суммарной толщиной. Выполнить условие задачи, используя только три подушки, нельзя.

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

Незаметно для друга Алиса узнала, что ему большего всего нравятся \(k\) различных цветов. Алиса приняла решение связать шарф размером \(n \times m\), в котором будут чередоваться полоски различных цветов. Её друг никогда не ищет легких путей, поэтому она решила, что шарф с горизонтальными или вертикальными полосками покажется ему слишком <<примитивным>>. Алиса решила, что полоски определённо должны быть диагональными!

Закончив вязать шарф, Алиса вспомнила, что один из \(k\) цветов её друг считает особенным! Это цвет \(c\), который по его мнению приносит школьникам удачу на олимпиадах по информатике. И Алисе стало невероятно интересно, сколько фрагментов шарфа имеют именно такой цвет. Шарф получился очень большим, Алиса очень устала, пока его вязала, поэтому сама она уже не может ответить на этот вопрос и просит вас о помощи...

Более формально шарф можно представить в виде таблицы размером \(n \times m\), каждая клетка которой покрашена в один из \(k\) цветов. Цвета нумеруются от \(1\) до \(k\).

Первая строка таблицы покрашена в цвета \(1\), \(2\), ..., \(k\), \(1\), \(2\), ..., \(k\) и т.д. Каждая следующая строка получена из предыдущей сдвигом влево на одну клетку. Таким образом, таблица состоит из диагональных полос.

При \(n = 4\), \(m = 8\) и \(k = 3\) таблица будет иметь следующий вид:

По данным числам \(n\), \(m\), \(k\) и \(c\) определите, сколько всего клеток покрашено в цвет \(c\).

Формат входных данных
Первая строка входных данных содержит натуральное число \(n\) — ширину шарфа.

Вторая строка входных данных содержит натуральное число \(m\) — длину шарфа.

Третья строка входных данных содержит натуральное число \(k\) — количество любимых цветов друга Алисы.

Числа \(n\), \(m\) и \(k\) не превосходят \(10^9\).

Четвёртая строка входных данных содержит натуральное число \(c\) — номер особенного цвета (\(1\le c \le k\)).

Формат выходных данных
Программа должна вывести одно целое число — количество клеток шарфа, которые покрашены в цвет \(c\).

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

Замечание

Картинка соответствует примеру из условия. Шарф имеет размеры \(4\times8\) и состоит из клеток трёх цветов. В цвет \(1\) покрашены \(11\) клеток.

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

Дети с интересом восприняли идею и вырезали из бумаги \(a\) звездочек и \(b\) снежинок. Теперь они планируют отправить их Санте Клаусу по почте. Им так понравились вырезанные ими украшения, что они, возможно, решат оставить себе часть. Таким образом, дети могут отправить Санте \(x\) звездочек и \(y\) снежинок, где \(0 \le x \le a\) и \(0 \le y \le b\). Чтобы Санта не расстроился, дети должны отправить ему хотя бы одно украшение. То есть должно выполняться также условие \(x + y > 0\).

Чтобы все олени выглядели красиво, на каждом должно оказаться одинаковое количество украшений. Известно, что у Санты \(n\) оленей, поэтому если будут отправлены \(x\) звездочек и \(y\) снежинок, величина \(x+y\) должна делиться на \(n\).

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

Формат входных данных

В одном наборе входных данных содержатся несколько тестов. Каждый тест следует решить независимо.
Первая строка входных данных содержит целое число \(t\) — количество тестов (\(1 \le t \le 10^5\)).

Следующие строки описывают тесты, по одному на строке. Описание теста состоит из трех целых чисел \(n\), \(a\) и \(b\) — количество оленей у Санты, количество звездочек и количество снежинок, вырезанных детьми (\(4 \le n \le 10^9\); \(0 \le a, b \le 10^9\)).

Формат выходных данных
Выведите \(t\) чисел. Для каждого теста выведите одно число: количество способов составить посылку для Санты Клауса.

Замечание
В первом тесте у Санты \(4\) оленя, а дети вырезали \(2\) звездочки и \(2\) снежинки. Здесь подходит только один набор — нужно отправить все вырезанные украшения.

Во втором тесте у Санты также \(4\) оленя, но дети вырезали \(4\) звездочки и \(4\) снежинки. Здесь подходит 6 наборов: 0 звездочек и 4 снежинки, 1 звездочка и 3 снежинки, 2 звездочки и 2 снежинки, 3 звездочки и 1 снежинка, 4 звездочки и 0 снежинок, а также 4 звездочки и 4 снежинки.

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

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

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

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

Входные данные

В первой строке входных данных содержится единственное целое число N — количество записей в журнале Василия (3 ≤ N ≤ 10⁵).

В следующих N строках записаны целые числа a_i, соответствующие записям в журнале (−10⁸ ≤ a_i ≤ 10⁸).

Выходные данные

Программа должна вывести единственное целое число — количество способов выполнить необходимое разбиение.

Примеры

Ввод	Вывод	Пояснение
6 4 3 -3 5 -1 4	2	В журнале записано 6 чисел: 4, 3, −3, 5, −1, 4 Из них можно получить два разбиения: [4], [3, −3, 5, −1], [4] и [4, 3, −3], [5, −1], [4].
3 0 0 0	1	В журнале записаны три нуля — имеется единственное возможное разбиение [0], [0], [0], потому что в каждой записи должно быть хотя бы одно число.
4 3 -2 3 1	0	Выполнить подходящее разбиение невозможно.

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

Формат входных данных
Единственная строка входного файла содержит натуральное число \(n\) (\(1 \le n \le 10^{18}\)).

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

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

 

В примере дано \(n = 25\). Число имеет в своей записи нечётную цифру \(5\), поэтому после первой операции \(n\) уменьшится на \(1\) и станет равно \(24\).

Число \(24\) не имеет в своей записи нечётных цифр, поэтому после второй операции \(n\) уменьшится в \(2\) раза и станет равно \(12\).

Далее \(n\) будет принимать значения: \(11\), \(10\), \(9\), \(8\), \(4\), \(2\), \(1\) и \(0\). Всего потребуется \(10\) операций.

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

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

Формат входных данных
В первой строке дано одно число \(n\) (\(1 \le n \le 10^5\)) — количество участников игры. Далее в \(n\) строках вводятся названные участниками натуральные числа, не превосходящие \(10^9\).

Формат выходных данных
Программа должна вывести число, написанное победителем. Если победителя нет, то нужно вывести число \(-1\).

Замечание

В первом примере из условия участвовали \(7\) игроков и они назвали числа \(5\), \(1\), \(1\), \(3\), \(4\), \(3\), \(1\). Сначала оставим только те числа, которые встречаются ровно один раз: \(5\) и \(4\). Минимальное из этих чисел равно \(4\).

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

Профессор Селезнев передает Алисе зашифрованную информацию, которая представляет собой последовательность целых чисел.  Все числа данной последовательности не превышают 10⁷. Каждое число передается в течении одной секунды. Чтобы понять, что данные переданы правильно, Алисе необходимо определить контрольное значение, которое вычисляется по следующему правилу,
- берутся три переданных значения из последовательности таким образом, чтобы между какими-либо двумя моментами передачи прошло ровно K секунд;
- вычисляется сумма выбранных чисел, которая должна быть минимальной. Данная сумма является контрольным значением.
Помогите Алисе определить контрольное значение.


Формат входных данных
В первой строке записано количество чисел N (1 ≤ N ≤ 2·105) и целое число K (1 ≤ K < 105, K < N). Каждая из следующих N строк содержит одно целое число, по модулю не превышающее 107.


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

Профессор Селезнев передает Алисе зашифрованную информацию, которая представляет собой последовательность целых чисел. Все числа данной последовательности не превышают 10⁷. Каждое число передается в течении одной секунды. Чтобы понять, что данные переданы правильно, Алисе необходимо определить контрольное значение, которое вычисляется по следующему правилу,
- берутся три переданных значения из последовательности таким образом, чтобы между между какими-либо двумя соседними моментами передачи прошло ровно K секунд (между передачей первого выбранного числа и второго или между передачей второго выбранного числа и третьего);
- вычисляется сумма выбранных чисел, которая должна быть минимальной. Данная сумма является контрольным значением.
Помогите Алисе определить контрольное значение.


Формат входных данных
В первой строке записано количество чисел N (1 ≤ N ≤ 2·105) и целое число K (1 ≤ K < 105, K < N). Каждая из следующих N строк содержит одно целое число, по модулю не превышающее 107.


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

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

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

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

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

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

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

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

Замечание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

Примечание

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

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

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

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

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

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

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

На клетчатой доске размером \(n \times m\), состоящей из \(n\) строк и \(m\) столбцов, в клетке \((r, c)\), то есть на пересечении \(r\)-й сверху строки и \(c\)-го слева столбца, расположена фишка. На этой доске вам предстоит сыграть против компьютера в игру, в которой можно перемещать фишку и удалять клетки поля.

Каждый ход устроен следующим образом.

1. Компьютер называет целое число \(k > 0\).

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

3. Компьютер называет координаты \((i, j)\) произвольной еще не удаленной клетки поля, после чего она сразу же удаляется.

Если компьютер удаляет клетку, на которой находится фишка, игра заканчивается вашей победой. Ваша цель — победить как можно раньше. При этом вы не сообщаете компьютеру свои перемещения, поэтому можете играть нечестно: вместо реального перемещения фишки по полю вы можете следить за всеми возможными ее положениями. Иными словами, если в какой-то момент при удалении клетки \((i, j)\) существует последовательность перемещений фишки, при которой в данный момент фишка находится в точности в клетке \((i, j)\), вы можете сообщить компьютеру, что игра завершена, и вы победили.

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

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

Формат входных данных
В единственной строке ввода даны четыре целых числа \(n\), \(m\), \(r\) и \(c\) — размеры доски и координаты изначального расположения фишки (\(1 \le r \le n \le 1000\); \(1 \le c \le m \le 1000\)).

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

В следующих \(n \cdot m\) строках даны ходы, которые последовательно собирается сделать компьютер. Описание \(t\)-го хода задается тремя целыми числами \(k_t\), \(i_t\) и \(j_t\) — количеством перемещений фишки, которые вам понадобится совершить, и координатами клетки поля, которую после этого требуется удалить (\(1 \le k_t \le 10^9\); \(1 \le i_t \le n\); \(1 \le j_t \le m\)).

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

Формат выходных данных
Выведите одно целое число от \(1\) до \(n \cdot m\) — номер хода, после которого вы сообщите компьютеру о своей победе.

 

В первом примере можно, например, первым ходом передвинуть фишку из \((1, 1)\) в \((1, 2)\), а вторым — из \((1, 2)\) в \((2, 2)\) и затем в \((2, 1)\), тем самым поместив ее на удаляемую клетку.