Информатика

Вася изготовил карточки, написав на них 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.

На координатной плоскости расположены равнобедренный прямоугольный треугольник ABC с длиной катета d и точка X. Катеты треугольника лежат на осях координат, а вершины расположены в точках: A (0,0), B (d,0), C (0,d).

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

Входные данные
Сначала вводится натуральное число d(не превосходящее 1000), а затем координаты точки X – два целых числа из диапазона от ­–1000 до 1000.

Выходные данные
Если точка лежит внутри, на стороне треугольника или совпадает с одной из вершин, то выведите число 0. Если точка лежит вне треугольника, то выведите номер вершины треугольника, к которой она расположена ближе всего (1 – к вершине A, 2 – к B, 3 – к C). Если точка расположена на одинаковом расстоянии от двух вершин, выведите ту вершину, номер которой меньше.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 1 1	0	Точка лежит внутри треугольника.
2	3 -1 -1	1	Точка лежит вне треугольника и ближе всего к ней вершина A
3	4 4 4	2	Точка лежит на равном расстоянии от вершин B и C,в этом случае нужно вывести ту вершину, у которой номер меньше, т.е. выведено должно быть число 2
4	4 2 2	0	Точка лежит на стороне треугольника.

Дано натуральное четырехзначное число. Найдите минимальное натуральное четырехзначное число, состоящее из тех же цифр, что и заданное. Заметим, что четырехзначные числа не могут начинаться с нуля.

Входные данные
Вводится натуральное четырехзначное число.

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

Примеры

№	Входные данные	Выходные данные
1	1513	1135

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

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



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

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

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

Примеры

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

Перед началом тараканьих бегов всем болельщикам было предложено сделать по две ставки на результаты бегов. Каждая ставка имеет вид "Таракан №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.

В Берляндии плачевная ситуация с междугородним автобусным сообщением. Во всей стране есть всего три автобусных маршрута, по каждому из которых курсирует лишь один автобус. В первый день нового года ровно в полночь все три автобуса отправляются по своим маршрутам из столицы Берляндии. Известно, что первому автобусу на то, чтобы проехать весь маршрут и вернуться в столицу требуется a минут, второму — b минут, а третьему — c минут. Таким образом, первый автобус отправляется из столицы Берляндии в моменты времени 0, a, 2a, 3a , второй — в моменты времени 0, b, 2b, 3b , а третий в моменты времени 0, c, 2c, 3c .

Момент времени называется подходящим для пересадки , если в этот момент все три автобуса отправляются из столицы Берляндии. Например если a=1, b=2, c=1, то моменты времени 0 и 2 являются подходящими для пересадки, а момент времени 1 не является, потому что в этот момент времени второй автобус находится в пути. Берляндия — особая страна с особым измерением времени, поэтому в берляндских сутках ровно t минут. Это означает, что в первый день происходят все моменты времени с 0-го по (t−1)-й включительно, во второй день — c t-го по (2t−1)-й включительно, в третий — с 2t-го по (3t−1)-й включительно и так далее.

Министерство транспорта Берляндии заинтересовалось, сколько подходящих для пересадки моментов времени произойдёт в d-й день в Берляндии. К сожалению, местные чиновники заняты другими делами, поэтому ответить на этот вопрос было поручено вам.

Входные данные
В пяти строках заданы пять целых чисел a, b, c, t  и d (1≤a, b, c≤10⁶ , 1≤t, d≤10⁹ ) — время полного прохождения маршрута первым, вторым и третьим автобусами, соответственно, количество минут в сутках и номер дня, которым интересуется министерство транспорта Берляндии.

Выходные данные
Выведите одно целое число — количество подходящих для пересадки моментов времени в d-й день.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	1 2 1 3 1	2	Сутки длятся 3 минуты, поэтому все моменты времени в день с номером 1 — это 0, 1, 2, из них моменты времени 0 и 2 являются подходящими для пересадки
2	2 3 4 7 2	1	Здесь рассматриваются вторые сутки с моментами времени 7, 8, 9, 10, 11, 12, 13. Первый автобус отправляется в моменты времени 8, 10, 12, второй автобус — в моменты времени 9 и 12, а третий — в моменты времени 8 и 12. Таким образом, только момент времени 12 является подходящим для пересадки.
3	2 3 4 3 3	0	Нет ни одного подходящего для пересадки момента времени

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

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

Сегодня у Кроша день рождения! По этому поводу он испек огромный торт. Торт представляет собой прямоугольник n × m , разделенный на nm единичных квадратиков горизонтальными и вертикальными линиями из крема.

На праздник в гости к Крошу пришли Совунья и Нюша. По законам гостеприимства, Крош должен поделиться с своим тортом. Для этого он хочет по очереди отрезать от торта два куска и раздать их гостьям.

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

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

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

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

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

Примеры

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

Примечание
Иллюстрация к тесту из примера: Крош делает разрезы вдоль пунктирных линий, отдавая гостьям куски с серыми границами. В конце ему достается кусок размера 2 × 3 .

 

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

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

Однако Егор не любит возрастающие последовательности. Его разочаровывают тройки башен, таких что с возрастанием их индексов их значения тоже возрастают. Более формально, тройка башен с номерами i , j и k разочаровывает Егора, если i < j < k и h_i < h_j < h k .

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

Входные данные
Первая строка входных данных содержит единственное число n — количество башен в Москве ( 1 ≤ n ≤ 8000 ).

Вторая строка входных данных содержит n различных натуральных чисел, i -е из них h i — высота i -й башни ( 1 ≤ h_i ≤ n ).

Выходные данные
Выведите одно число — количество троек башен, которые разочаруют Егора.

Обратите внимание, что ответ может не поместиться в стандартный 32-битный тип данных. Надо использовать 64-битный тип, в паскале он называется « int64 », в C++ « long long », в Java « long ».
 

Примеры

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

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

К сожалению, первый же квест в игре поставил Петю в тупик. Выполнив задание, он получил n магических артефактов, которые можно использовать для получения золота. Для каждого артефакта известна его ценность , для i -го артефакта она равна w_i . Для получения золота артефакты можно активировать . Каждый артефакт можно активировать только один раз. Петя может активировать артефакты в произвольном порядке.

У героя, которым управляет Петя, есть магическая сила , исходно она равна нулю. Есть два способа активировать артефакт: с помощью магии и с помощью силы. Если активировать артефакт с ценностью w с помощью магии, то магическая сила героя увеличивается на w . Если же активировать артефакт с ценностью w с помощью силы, то герой получает xw золотых монет, где x — магическая сила героя в момент активации артефакта.

Например, если герой Пети получил 4 артефакта с ценностями 1, 1, 2 и 2, то можно получить 9 золотых монет, действуя следующим образом. Сначала надо активировать с помощью магии по одному артефакту с ценностью 1 и 2. После этого магическая сила героя равна 3, теперь можно активировать с помощью силы оставшиеся артефакты и получить 3 и 6 золотых монет, соответственно.

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

Входные данные
Первая строка входных данных содержит единственное число n — количество магических артефактов ( 1 ≤ n ≤ 100 ).

Вторая строка входных данных содержит n чисел w₁ , w₂ , ..., w_n — ценности артефактов ( 1 ≤ w_i ≤ 100 ).

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

Примеры

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