Информатика

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

Рассмотрим упрощённый вариант этой игры. Пусть игрок может сделать один щелчок мышкой в секунду, что приносит ему одну печеньку. Также в любой момент времени игрок может потратить C печенек на покупку фабрики (при этом у игрока должно быть не меньше C печенек, после покупки фабрики количество его печенек моментально уменьшается на C ). Каждая купленная фабрика увеличивает ежесекундное производство печенек на P штук (то есть если у игрока одна фабрика, то он получает 1  + P печенек в секунду, две фабрики — 1  +  2 P печенек, три фабрики — 1  +  3 P печенек и т. д.). Игрок может приобрести неограниченное число фабрик стоимостью C печенек каждая. Фабрика начинает производить дополнительные печеньки сразу же, например, если после какой-то секунды игры у игрока стало C печенек, то игрок может купить фабрику и уже на следующей секунде его производство печенек увеличится на P штук.

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

Входные данные
Программа получает на вход три целых положительных числа, записанных в отдельных строках: С (стоимость фабрики), P (производительность одной фабрики) и N (необходимое количество печенек).

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	50 3 100	75	Через 50 секунд после начала игры у игрока будет 50 печенек, и он сможет купить фабрику. После этого он будет получать 4 печеньки в секунду, и на производство 100 печенек понадобится еще 25 секунд.
2	99 10 100	100	Игрок сможет набрать 100 печенек за 100 секунд, при этом фабрику покупать нет смысла.

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

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


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

Выходные данные
Программа получает на вход два числа 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

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

Фирма, готовая размножить печатные материалы, предлагает следующие финансовые условия. Один лист она печатает за A1 рублей, 10 листов — за A2 рублей, 100 листов — за A3 рублей, 1000 листов — за A4 рублей, 10 000 листов — за A5 рублей, 100 000 листов — за A6 рублей и 1 000 000 листов — за A7 рублей. При этом не гарантируется, что один лист в более крупном заказе обойдется дешевле, чем в более мелком. И даже может оказаться, что для любой партии будет выгодно воспользоваться тарифом для одного листа.

Печать конкретного заказа производится или путем комбинации нескольких тарифов, или путем заказа более крупной партии. Например, 980 листов можно распечатать, заказав печать 9 партий по 100 листов плюс 8 партий по 10 листов, сделав 98 заказов по 10 листов, 980 заказов по 1 листу или заказав печать 1000 (или даже 10 000 и более) листов, если это окажется выгоднее.

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

Входные данные
На вход программе сначала подается число N (1 ≤ N ≤ 2 × 109) — количество листов в заказе. В следующих 7 строках ввода находятся натуральные числа A1, A2, A3, A4, A5, A6, A7 соответственно (1 ≤ Ai ≤ 106).

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

Примеры

№	Входные данные	Выходные данные
1	980 1 9 90 900 1000 10000 10000	882
2	980 1 10 100 1000 900 10000 10000	900

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

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

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

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

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

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

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

Примеры

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

Рассмотрим последовательности чисел. Первая последовательность состоит из одного числа 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 (N не превышает 26).

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

Примеры

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

В новой программе 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.

Перед началом тараканьих бегов всем болельщикам было предложено сделать по две ставки на результаты бегов. Каждая ставка имеет вид "Таракан №A придет раньше, чем таракан №B".

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

Входные данные
В первой строке входных данных содержатся два разделенных пробелом натуральных числа: число K, не превосходящее 10, - количество тараканов и число N, не превосходящее 100, - количество болельщиков. Все тараканы пронумерованы числами от 1 до K. Каждая из следующих N строк содержит 4 натуральных числа A, B, C, D, не превосходящих K, разделенных пробелами. Они соответствуют ставкам болельщика "Таракан №A придет раньше, чем таракан №B" и "Таракан №C придет раньше, чем таракан №D".

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

Если требуемого результата добиться нельзя, выведите одно число 0.

Примеры

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

Примечание: Решения задачи на языке программирования Python не проходят ограничения по времени.

Фирма NNN решила транслировать свой рекламный ролик в супермаркете XXX. Однако денег, запланированных на рекламную кампанию, хватило лишь на две трансляции ролика в течение одного рабочего дня.

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

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

Если трансляция ролика включается, например, в момент времени 10, то покупатели, пришедшие в супермаркет в момент времени 10 (или раньше) и уходящие из супермаркета в момент 15 (или позднее) успеют его прослушать целиком, а, например, покупатель, пришедший в момент времени 11, равно как и покупатель, уходящий в момент 14 - не успеют. Если покупатель успевает услышать только конец первой трансляции ролика (не сначала) и начало второй трансляции (не до конца), то считается, что он не услышал объявления. Если покупатель успевает услышать обе трансляции ролика, то при подсчете числа людей, прослушавших ролик, он все равно учитывается всего один раз (фирме важно именно количество различных людей, услышавших ролик).

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

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 1 11 1 3 6 15 1 6	3 1 6	Трансляция роликов начинается в моменты времени 1 и 6. Первое объявление успевают прослушать покупатели номер 1 и 4, второе - 1 и 3. Когда бы ни начиналась трансляция объявления, 2-й покупатель не сможет его прослушать, так как находится в супермаркете менее 5 минут. Приведенный ответ является не единственным верным ответом на этот тест.
2	1 1 10	1 3 25	Объявление, трансляция которого начинается в момент 3, единственный покупатель обязательно услышит. Вторую трансляцию (раз она оплачена) мы можем сделать когда угодно, например, в 25 минут в пустом супермаркете (впрочем, мы не можем начать трансляцию второго объявления, например, в момент 7 - т.к. к этому моменту еще не закончится первая трансляция)
3	3 1 10 11 20 21 30	2 1 22	Объявление услышат лишь 2 из 3-х покупателей.

Как известно, не только люди любят принимать участие в различных соревнованиях. Среди рыб и моллюсков также проводится множество состязаний на дне океана. Акула Семён участвует в самом престижном соревновании Мирового океана на звание самой опасной акулы. Во время этого состязания акулы соревнуются в различных дисциплинах: плавание на скорость, маскировка, навигация по картам и многим другим. Сейчас Семён проходит испытание под названием «разрушение».

Во время этого испытания перед акулой ставят m доминошек. Все доминошки стоят на одной прямой, однако высоты доминошек могут различаться. Расстояние между соседними доминошками равно 1. Кроме того, у каждой доминошки есть своя стоимость, выраженная целым числом. Цель акулы — уронить все доминошки. Для этого акула может толкнуть любую доминошку влево или вправо, после чего она начнёт падать в этом направлении. Если во время падения доминошка задевает другие, они также начинают падать в ту же сторону, в которую падала исходная, таким образом начинается цепная реакция, в результате которой может упасть множество доминошек. Падающая доминошка задевает другую, если и только если расстояние между ними строго меньше высоты падающей доминошки, причем доминошки не обязательно должны быть соседними.

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

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

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

В первой строке заданы два целых числа n и m (1 ≤ n≤ 250 000, 1 ≤ m ≤ 10⁷ ) — количество блоков и суммарное количество доминошек, которые надо уронить Семёну, соответственно.

Затем следует описание n блоков. Описание каждого блока состоит из трёх строк.

В первой строке описания блока с номером i содержится целое число k_i (1 ≤ k_i ≤ 250000, \(\sum_{i=1}^n {k_i ? 250 000}\) ) — количество доминошек в блоке.

Во второй строке описания блока с номером i содержатся ki целых чисел a_i,j (1 ≤ a_i,j ≤ m) — высоты доминошек в блоке.

В третьей строке описания блока с номером i содержатся ki целых чисел c_i,j (1 ≤ c_i,j ≤ 100000) — стоимости доминошек в блоке.

Далее следует описание последовательности доминошек, которые надо уронить Семёну, в порядке слева направо.

В первой строке описания последовательности задано целое число q (n ≤ q ≤ 250000) — количество блоков в последовательности доминошек, которые надо уронить.

В следующих q строках содержатся пары целых чисел id_i mul_i (1 ≤ id_i ≤ n, 1 ≤ mul_i ≤ 100000), обозначающие, что очередные k_idi в порядке слева направо доминошек — это доминошки блока id_i, чьи стоимости были умножены на число mul_i.

Гарантируется, что \(\sum_{i=1} ^q k_{id_i} = m\) , а также, что каждый блок встречается хотя бы один раз в последовательности доминошек, которые требуется уронить, то есть для всех i от 1 до n найдется j такое, что id_j=i.

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

Примечание
В первом примере перед Семёном стоят 7 доминошек. Их высоты равны [3122122] , а стоимости равны [4363121] . Сначала Семёну следует уронить доминошку с номером 7 влево, она упадёт и заденет доминошку с номером 6. Доминошка 6, падая, заденет доминошку с номером 5, которая упадёт, но не заденет другие доминошки. Затем Семён должен уронить доминошку с номером 1 вправо, она, падая, заденет доминошки с номерами 2 и 3, а доминошка 3, падая, заденет доминошку 4, таким образом все доминошки упадут.

Во втором примере перед Семёном стоит одна доминошка стоимостью 10000000000.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	2 7 3 1 2 2 1 2 1 1 3 2 3 2 2 1 3 1 1	5	Перед Семёном стоят 7 доминошек. Их высоты равны [3122122] , а стоимости равны [4363121] . Сначала Семёну следует уронить доминошку с номером 7 влево, она упадёт и заденет доминошку с номером 6. Доминошка 6, падая, заденет доминошку с номером 5, которая упадёт, но не заденет другие доминошки. Затем Семён должен уронить доминошку с номером 1 вправо, она, падая, заденет доминошки с номерами 2 и 3, а доминошка 3, падая, заденет доминошку 4, таким образом все доминошки упадут.
2	1 1 1 1 100000 1 1 100000	10000000000	Перед Семёном стоит одна доминошка стоимостью 10000000000

Рома и Денис отправились на соревнование по программированию. В долгой дороге ребята вспоминали операции над строками. Денис сказал, что в Python строки можно умножать на число, тогда Рома, программирующий на С++, решил придумать операцию перемножения строк. По версии Ромы, умножение строки s длины n на строку t обозначается как s·t и равно строке t+s₁+t+s₂+...+t+s_n+t, где s_i обозначает i-й символ строки s, а знаком « + » обозначено сложение (конкатенация) строк. Например, произведением строк « abc » и « de » является строка « deadebdecde », а произведением строк « z » и « ab » является строка « abzab ». Обратите внимание, что, в отличие от умножения чисел, произведение строк s и t, вообще говоря, не равно произведению строк t и s.

Денис решил продолжить мысль Ромы — он, как ценитель прекрасного, решил определить красоту строки как максимальную длину подряд идущей группы одинаковых букв. Например, красота строки « xayyaaabca » равна 3, так как самая длинная группа подряд идущих одинаковых букв — это « aaa », а красота строки « qwerqwer » равна 1, потому что все соседние буквы в ней различны.

Чтобы развлечь Дениса, Рома написал ему на листочке n строк p₁,p₂, p₃, ... ,p_n и попросил его вычислить красоту строки (...((p₁·p₂)·p₃)·...)p_n. Денис не до конца понял, как работает умножение Ромы, но не хочет признаваться в этом, поэтому просит посчитать красоту этой строки вас. Рома знает, что Денис слишком впечатлительный, поэтому гарантирует, что красота полученной строки не превосходит 10⁹.

Входные данные
В первой строке содержится число n (1 ≤ n ≤ 100000) — количество строк, которые написал Рома.

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

Гарантируется, что суммарная длина строк не превосходит 100000, а также, что красота произведения всех строк не превосходит 10⁹.

Выходные данные
Выведите одно целое число — красоту произведения строк.
 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 a b a	3	произведение трёх строк равно « abaaaba »
2	2 bnn a	1	произведение двух строк равно « abanana »

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

Более формально, пусть n детей выстроились в хоровод. Пронумеруем их целыми числами от 1 до n так, чтобы справа от ребёнка с номером i стоял ребёнок с номером i+1, а справа от ребёнка с номером n стоял ребёнок с номером 1. Тогда неудобством этого хоровода назовём максимальную разность между ростом детей, которые стоят рядом. Обратите внимание, что разностью в росте двух детей называется разность между ростом более высокого и более низкого ребёнка, таким образом, разность в росте двух детей всегда неотрицательна.

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

Входные данные
В первой строке содержится одно целое число n (2 ≤ n≤ 10⁵) — количество детей, которые пришли на день рождения ковбоя Влада.

Во второй строке заданы n целых чисел a_i (1≤a_i≤10⁹) — рост каждого из детей. Рост детей задан в нанометрах и уменьшен на 10⁹, таким образом, рост ребёнка с a_i=1 чуть выше метра, а рост ребёнка с a_i=10⁹ составляет два метра.

Выходные данные
Выведите n целых чисел — значения роста детей в порядке, в котором они должны встать в хоровод. В этом порядке соседними будут дети с номерами i и i+1, а также дети с номерами 1 и n. Если оптимальных хороводов несколько, то выведите любой из них.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	5 2 1 1 3 2	1 2 3 2 1	Здесь неудобство хоровода равно 1, так как разность в росте между соседними детьми равна 1, 1, 1, 1 и 0 соответственно. Обратите внимание, что последовательности [23211] , [32112]  задают те же хороводы и отличаются только выбором ребёнка с номером 1.
2	3 30 10 20	10 30 20	Неудобство хоровода равно 20, так как разность в росте детей высотой 10 и 30 равна 20.

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

Автомат представляет собой последовательность из блоков двух типов: максимизаторов и минимизаторов . На каждом блоке написано некоторое натуральное число 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

Миша установил на свой телефон новую игру «Мемтест 2к17». В ней предусмотрены ежедневные награды за посещение. Награды бывают n уровней. Тип награды зависит от награды за предыдущий день, а именно:

если игрок в предыдущий день не посещал игру, то за сегодняшнее посещение он получит награду уровня 1;
если игрок в предыдущий день зашёл в игру и получил награду уровня k ( k ≠ n ), то за сегодняшнее посещение он получит награду уровня k + 1 ;
если игрок в предыдущий день зашёл в игру и получил награду уровня n , то за сегодняшнее посещение он получит награду уровня 1.
На Форуме для Крутых Программистов Миша выяснил, что награды каждого из уровней составляют соответственно a 1 , a 2 , ..., a n золотых монет.
Через m дней состоится турнир по «Мемтест 2к17», к которому Миша хочет собрать как можно больше золотых монет. Помогите ему спланировать посещения игры на протяжении m дней, оставшихся до турнира. Найдите наибольшее количество золотых монет, которое он сможет получить за счёт ежедневных наград в этот период. Можно считать, что игра установлена в первый из этих m дней, то есть до этого Миша в неё ни разу не заходил.

Входные данные
Первая строка входных данных содержит натуральные числа n и m ( 1 ≤ n , m ≤ 1000 ) — количества уровней наград и дней до турнира.

Вторая строка входных данных содержит n целых чисел a 1 , a 2 , ..., a n ( 1 ≤ a i ≤ 1000 ), где a i — величина награды i -го уровня в золотых монетах.

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

Примечание
В первом тесте из примера Мише выгодно заходить в игру каждый день. Тогда он получит 1 + 2 + 4 = 7 золотых монет.

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

Примеры

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

У доктора Риты сегодня трудный рабочий день, и она ушла на обеденный перерыв. За это время к ее кабинету выстроилась очередь из n человек! Очередь большая, поэтому в помещении быстро стало очень душно.

Для удобства пронумеруем пациентов натуральными числами от 1 до n в том порядке, в котором они изначально стояли в очереди: первым стоял человек с номером 1 , вторым — с номером 2 , и так далее. Последним был человек с номером n .

Далее, пока Рита не вернулась с обеда, t раз происходило следующее событие: кому-то из очереди становилось очень душно. Из-за этого он выходил на улицу подышать свежим воздухом, и тут же возвращался обратно, вставая в конец очереди.

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

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

Входные данные
В первой строке входных содержатся два числа n и t — число людей в очереди и количество событий, что человек вышел на улицу подышать ( 1 ≤ n , t ≤ 100 000 ).

Во второй строке входных данных содержатся t чисел a i ( 1 ≤ a_i ≤ n ) — номера людей, выходивших подышать и затем встававших в конец очереди в том порядке, в котором они это делали.

Выходные данные
Выведите n чисел — номера людей в порядке очереди после всех перестановок.

Примечание
В тесте из примера происходили следующие изменения с очередью:

Человек с номером 2 перешёл в конец. Порядок людей: 1 , 3 , 4 , 2
Человек с номером 3 перешёл в конец. Порядок людей: 1 , 4 , 2 , 3
Человек с номером 1 перешёл в конец. Порядок людей: 4 , 2 , 3 , 1
Человек с номером 2 перешёл в конец. Порядок людей: 4 , 3 , 1 , 2
Человек с номером 1 перешёл в конец. Порядок людей: 4 , 3 , 2 , 1
Порядок людей в очереди в конце: 4 , 3 , 2 , 1 .
 

Примеры

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

Беда! К городу N приближается метеорит. Людей уже успели эвакуировать, но домам урона не избежать. Ученые уже выяснили, куда упадет метеорит. Вас, как сотрудника страховой компании, попросили выяснить количество домов, которые пострадают при падении метеорита.

Введём на плоскости прямоугольную систему координат. Город представляет собой прямоугольник n × m . Его левый нижний угол расположен в точке с координатами (0, 0) , а правый верхний угол в точке с координатами ( n - 1, m - 1) . В каждой точке с целыми координатами внутри или на границе этого прямоугольника находится дом. Дома в городе N маленькие, поэтому их можно считать точками.

Известно, что метеорит упал в точку ( x , y ) , а радиус его поражения равен r . Таким образом, все дома города на расстоянии не более r от точки падения метеорита получат повреждения. Найдите количество домов, которые получат повреждения.

Входные данные
Первая строка содержит два целых числа n , m ( 1 ≤ n , m ≤ 500 ) — размеры города N.

Вторая строка содержит три целых числа x , y , r ( - 500 ≤ x , y ≤ 500 ; 0 ≤ r ≤ 500 ) — координаты точки падения метеорита и радиус поражения, соответственно.

Выходные данные
Выведите одно число — количество повреждённых домов.

Примечание
Иллюстрация к тесту из примера: чёрными точками обозначены повреждённые дома, белыми — уцелевшие.

Примеры

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

Марина очень любит палиндромы. Палиндром — это строка, которая одинаково читается слева направо и справа налево, например « noon », « rotator » или « radar ».

Марина написала на доске строку s , состоящую из n строчных латинских букв s₁ s₂ ... s_n . Подстрокой строки s называется строка s _{ls l + 1} ... s_r для некоторых 1 ≤ l ≤ r ≤ n . Марина ищет в строке s как можно более длинную подстроку, которая является палиндромом. Например, в строке « rotateradars » такой подстрокой будет « radar ».

Вова хочет изменить написанную Мариной строку, чтобы подстрока-палиндром была как можно длиннее. Он может либо оставить строку нетронутой, либо изменить в ней ровно одну букву на другую. Например, если в строке « rotateradars » изменить шестую букву на « o », получится строка « rotatoradars », в которой максимальная подстрока-палиндром « rotator » имеет длину 7 . Подстроку-палиндром большей длины получить нельзя.

Помогите Вове определить, какую максимальную длину подстроки-палиндрома он сможет получить.

Входные данные
Первая строка входных данных содержит натуральное число n — длину строки, которую написала Марина ( 1 ≤ n ≤ 100 ).

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

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

Примеры

№	Входные данные	Выходные данные
1	12 rotateradars	7

Игорь читает новостную ленту в своей любимой социальной сети, состоящую из n последовательно расположенных записей. Каждая запись в ленте имеет свою характеристику — позитивность a_i , заданную натуральным числом. После прочтения i -й записи настроение Игоря улучшается на a_i .

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

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

Входные данные
Первая строка содержит два числа n и p ( 1 ≤ n ≤ 1000 , 1 ≤ p ≤ 10⁷ ) — количество записей в новостной ленте и величину, на которую Игорь хочет увеличить своё настроение.

Вторая строка содержит n целых неотрицательных чисел a i ( 1 ≤ a_i ≤ 10⁴ ) — позитивности записей в ленте. Соседние числа разделены ровно одним пробелом.

Выходные данные
Если Игорь сможет стать счастливым, выведите два числа — номер записи k , с которой следует начать просмотр, и количество записей c , которые нужно посмотреть. Если возможных ответов с минимальным c несколько, выведите тот, у которого k минимально.

Если же решения нет, выведите - 1.
 

Примеры

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