Васе стало интересно, сколько его любимый ноутбук потребляет электроэнергии за день. У его ноутбука есть три режима. В режиме нормальной работы он потребляет P₁ Вт в минуту. Через T₁ минут после того, как Вася с последний раз двинул мышью или нажал кнопку на клавиатуре, на дисплее запускается скринсейвер и потребление энергии меняется до P₂ Вт в минуту. И, наконец, через T₂ минут после запуска скринсейвера ноутбук переходит в режим "сна", в котором потребляет P₃ Вт в минуту. Если Вася двигает мышью или касается клавиатуры в момент, когда ноутбук находится во втором или в третьем режимах, ноутбук возвращается в первый режим энергопотребления. Работу Васи за ноутбуком можно разбить на n временных отрезков [l₁, r₁], [l₂, r₂], ..., [l_n, r_n], в течение которых он только и делал, что работал мышью и нажимал на клавиатуру, а в промежутках между ними ничего этого не делал. Посчитайте, какое суммарное количество энергии было потреблено ноутбуком за период [l₁, r_n].

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

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

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

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

Биджану в это верится с трудом. А вам?

Ивестный певец Арьё, собирается выпустить новый альбом своих великих произведений!

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

У него есть список всех использованных названий для альбомов вместе с годом, когда данные альбомы были опубликованы. Также у него есть список подходящих названий для своего альбома.

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

Помогите ему назвать альбом.

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

Валидным размером футболки называют либо «M», либо от \(0\) до \(3\) «X», за которыми следуют «S» или «L». Например, размеры «M», «XXS», «L», «XXXL» валидны, а «XM», «Z», «XXXXL» не валидны.

И в прошлом году, и в этом в кубке \(n\) победителей. У Ксении есть список размеров футболок, которые печатались к прошлому году, и теперь ей надо отправить новый список в типографию.

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

Какое минимальное количество секунд потребуется Ксении, чтобы изменить список прошлого года на список текущего?

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

У Поликарпа есть \(n\) монет, достоинство \(i\)-й монеты равно \(a_i\). Поликарп хочет распределить монеты по своим карманам, но он не может класть две монеты одинакового достоинства в один и тот же карман.

Например, елси у Поликарпа есть шесть монет, представленных в виде массива \(a = [1, 2, 4, 3, 3, 2]\), он может распределить их по двум карманам следующим образом: \([1, 2, 3], [2, 3, 4]\).

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

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

Страна, в которой живет Соня, представляет собой бесконечную прямую. В каждой целочисленной координате на этой прямой находится город. У девочки есть \(n\) отелей, \(i\)-й отель находится в городе с координатой \(x_i\). Соня — девочка умная, поэтому, она не открывает два или более отеля в одном городе.

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

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

Так как Соня так же увлекается и робототехникой, она решила построить роботов, которые будут считывать числа и распознавать их.

Соня нарисовала в ряд \(n\) чисел, где на \(i\)-й позиции находится число \(a_i\). Она так же поставила по роботу в каждый конец ряда (слева от первого числа и справа от последнего). Соня даст каждому роботу по одному числу (они могут быть как одинаковые, так и различны) и запустит их. Когда робот запущен, он движется навстречу другому роботу, считывая числа в ряду. Когда робот считывает число, которое равно тому числу, что ему ввели, он выключится и останется на этой же позиции.

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

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

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

Соне теперь стало интересно, сколько различных пар чисел можно дать роботам так, чтобы они не встретились. То есть, если есть пара чисел (\(p\), \(q\)), то девочка даст число \(p\) первому роботу, а \(q\) второму. Пары чисел (\(p_i\), \(q_i\)) и (\(p_j\), \(q_j\)) считаются различными, если \(p_i\neq p_j\) или \(q_i\neq q_j\).

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

Маленькая девочка Таня поднимается по лестницам внутри многоэтажного дома. Каждый раз, когда она идет по очередной лестнице, она начинает считать ступеньки от \(1\) до количества ступенек в этой лестнице. Все числа она произносит вслух. Например, если она поднимется по двум лестницам, первая из которых содержит \(3\) ступеньки, а вторая — \(4\) ступеньки, то она произнесет вслух числа \(1, 2, 3, 1, 2, 3, 4\).

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

Последовательность \(a_1, a_2, \dots, a_n\) называется хорошей, если для любого его элемента \(a_i\) найдется такой элемент \(a_j\) (\(i \ne j\)), что \(a_i+a_j\) является степенью двойки (то есть равен \(2^d\) для некоторого неотрицательного целого \(d\)).

Например, следующие последовательности — хорошие:

• \([5, 3, 11]\) (например, для \(a_1=5\) можно выбрать \(a_2=3\), что сумма — степень двойки, подобную пару можно найти и для \(a_2\) и \(a_3\)),
• \([1, 1, 1, 1023]\),
• \([7, 39, 89, 25, 89]\),
• \([]\).

Обратите внимание, что по определению пустая последовательность (то есть такая, длина которой равна \(0\)) является хорошей.

Например, следующие последовательности не являются хорошими:

• \([16]\) (для \(a_1=16\) невозможно найти другой элемент \(a_j\), что их сумма — степень двойки),
• \([4, 16]\) (для \(a_1=4\) невозможно найти другой элемент \(a_j\), что их сумма — степень двойки),
• \([1, 3, 2, 8, 8, 8]\) (для \(a_3=2\) невозможно найти другой элемент \(a_j\), что их сумма — степень двойки).

Задана последовательность \(a_1, a_2, \dots, a_n\). Какое наименьшее количество элементов надо удалить, чтобы сделать её хорошей? Удалять можно произвольный набор элементов.

Поликарп тренирует свое умение решать задачи. У него есть список из \(n\) задач со сложностями \(a_1, a_2, \dots, a_n\) соответственно. Его план состоит в том, чтобы тренироваться ровно \(k\) дней. Каждый день он должен решать хотя бы одну задачу из своего списка. Поликарп решает задачи в том порядке, в котором они заданы в списке, и он не может пропустить какую-либо задачу из списка. Он должен решить ровно \(n\) задач ровно за \(k\) дней.

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

Полезность \(j\)-го дня тренировки Поликарпа равна максимальной сложности задачи среди всех задач, которые Поликарп решит в течение \(j\)-го дня (то есть если он решит задачи с номерами от \(l\) до \(r\) в течение какого-то дня, тогда полезность этого дня равна \(\max\limits_{l \le i \le r}a_i\)). Общая полезность его тренировки — это сумма полезностей по всем \(k\) дням его тренировки.

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

Например, если \(n = 8, k = 3\) и \(a = [5, 4, 2, 6, 5, 1, 9, 2]\), одним из возможных способов с максимальной общей полезностью является следующий: \([5, 4, 2], [6, 5], [1, 9, 2]\). Здесь общая полезность равна \(5 + 6 + 9 = 20\).

Витя начал учить берляндский язык. Известно, что в Берляндии используют латинский алфавит. Буквы «a», «o», «u», «i» и «e» являются гласными. Остальные буквы — согласные.

В берляндском языке после каждой согласной буквы обязательно идёт гласная буква, а после гласной — может идти любая. Единственным исключением является согласная буква «n» — после неё может идти любая буква (не только гласная), а может и не идти буква вообще. Например, слова «harakiri», «yupie», «man» и «nbo» являются берляндскими, а слова «horse», «king», «my» и «nz» — нет.

Помогите Вите понять, является ли слово \(s\) берляндским.

Задана троичная строка (строка, состоящая только из символов '0', '1' и '2').

Можно обменивать местами любую пару соседних (последовательных) символов '0' и '1' (то есть заменять «01» на «10» и наоборот) или любую пару соседних (последовательных) символов '1' и '2' (то есть заменять «12» на «21» и наоборот). Другие обмены запрещены.

Например, со строкой «010210» можно проводить следующие действия:

• «010210» \(\rightarrow\) «100210»;
• «010210» \(\rightarrow\) «001210»;
• «010210» \(\rightarrow\) «010120»;
• «010210» \(\rightarrow\) «010201».

Заметим, что нельзя менять местами «02» \(\rightarrow\) «20» и наоборот. Также нельзя проводить никаких других операций со строкой, за исключением тех, что описаны выше.

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

Строка \(a\) лексикографически меньше строки \(b\) (если строки \(a\) и \(b\) имеют одинаковую длину), если найдется такая позиция \(i\) (\(1 \le i \le |a|\), где \(|s|\) — длина строки \(s\)), что для всех \(j < i\) выполняется \(a_j = b_j\), и \(a_i < b_i\).

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

Логические элементы бывают четырех видов: AND (И, \(2\) входа), OR (ИЛИ, \(2\) входа), XOR (исключающее ИЛИ, \(2\) входа), NOT (НЕ, \(1\) вход). Логические элементы принимают значения со своих прямых потомков (входов) и возвращают результат функции, которую они выполняют. Наташе известна логическая схема марсохода, а также то, что в ней сломался ровно один вход. Чтобы починить марсоход, ей нужно изменить значение на этом входе.

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

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

Всего на складе доступны \(m\) суточных комплектов питания. Каждый комплект характеризуется своим типом \(a_i\).

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

Формально, для каждого участника \(j\) Наташа должна выбрать тип питания \(b_j\) и каждый день \(j\)-й участник дожен съедать комплект питания типа \(b_j\). Значения \(b_j\) у разных участников могут как различаться, так и совпадать.

Какой максимальной продолжительности в днях можно спланировать экспедицию, чтобы выполнить требования выше?

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

Для каждой поездки Глебу известны три числа: номер первого дня поездки s_i, продолжительность поездки в днях len_i и количество дней t_i, которое консульство соответствующей страны тратит на оформление визы. Глеб имеет P (1 ≤ P ≤ 2) действующих паспортов и может решать, в какой паспорт проставлять какую визу.

В каждую поездку Глеб улетает рано утром для s_i и возвращается поздно вечером дня s_i + len_i - 1.

Чтобы подать паспорт на визу в день d, Глебу нужно быть в Иннополисе в середине соответствующего дня. Поэтому он не может подавать на визу, пока он в другой поездке, включая ее первый и последний день. Если поездка начинается на следующий день после окончания предыдущей, Глеб не может подать на визу между ними. Самое раннее, когда Глеб может подать на визу  — это день номер 1.

После подачи на визу страны i в день d Глеб получит паспорт назад в середине дня d + t_i. Консультсва используют службы доставки, поэтому он может получить свой паспорт, даже если находится в поездке в этот день. Но Глеб может подать паспорт на другую визу в день получения паспорта, но только если в этот день он находится в Иннополисе в этот день.

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

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

Задан набор из \(n\) отрезков на оси \(Ox\), каждый отрезок имеет целочисленные координаты концов от \(1\) до \(m\) включительно. Отрезки могут пересекаться, вкладываться или даже совпадать друг с другом. Каждый отрезок характеризуется двумя целыми числами \(l_i\) и \(r_i\) (\(1 \le l_i \le r_i \le m\)) — координатами левого и правого концов.

Рассмотрим все целочисленные точки между \(1\) и \(m\) включительно. Ваша задача — вывести все точки из этого множества, не принадлежащие ни одному отрезку. Точка \(x\) принадлежит отрезку \([l; r]\) тогда и только тогда, когда \(l \le x \le r\).

Вам досталась тетрадь, которая называется Тетрадь Смерти. В ней бесконечное количество страниц. На последней странице этой тетради (хех) написано правило. Оно гласит: «Вы должны записывать в эту тетрадь имена в течение \(n\) последовательных дней. В течение \(i\)-го дня вы должны записать ровно \(a_i\) имен.». Вы очень испугались (конечно вы испугались, кто бы не испугался, если бы он получил тетрадь, которая называется Тетрадь Смерти, с каким-то странным правилом, написанным в ней?).

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

Теперь вас интересует следующий вопрос: сколько раз вы перевернете страницу в течение каждого дня? Вы заинтересованы в количестве переворотов страницы в течение каждого дня от \(1\) до \(n\).

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

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

Помогите Васе! Сообщите ему максимальный суммарный вес грибов, который он может собрать.

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

Задано два числа \(a\) и \(b\) в двоичной системе счисления, их длина равна \(n\). Сколько есть различных способов поменять местами два бита в числе \(a\) (только в \(a\), не в \(b\)) так, чтобы побитовое ИЛИ чисел изменилось? Другими словами, пусть \(c\) равно побитовому ИЛИ \(a\) и \(b\), тогда вам нужно найти количество способов поменять местами два бита в \(a\) так, чтобы побитовое ИЛИ не было равно \(c\).

Обратите внимание, что числа могут содержать ведущие нули, так что длина каждого числа равна \(n\).

Побитовое ИЛИ — это бинарная операция. Результат — это такое число, в двоичном представлении которого в каждом разряде стоит единица, если единица находится в двоичной записи хотя бы одного из аргументов. Например, \(01010_2\) ИЛИ \(10011_2\) = \(11011_2\).

К вашему удивлению, вы не Рудольф, и вам не нужно помогать ему\(\ldots\) Вы — сотрудник службы безопасности! Пожалуйста, найдите количество способов поменять местами два бита в \(a\) так, чтобы побитовое ИЛИ изменилось.

Задано две строки \(s\) и \(t\). Строка \(s\) состоит из строчных букв латинского алфавита и не более одного символа звездочки '*', строка \(t\) состоит только из строчных букв латинского алфавита. Длина строки \(s\) равна \(n\), длина строки \(t\) равна \(m\).

Символ зведочки '*' в строке \(s\) (если он есть) можно заменить на произвольную последовательность символов (возможно, пустую) строчных латинских букв. Другие символы строки \(s\) ни на что заменять нельзя. Если после такой замены в \(s\) можно получить строку \(t\), то говорят, что строка \(t\) соответствует шаблону \(s\).

Например, если \(s=\)«aba*aba», то такому шаблону соответствуют строки «abaaba», «abacaba», «abazzzzaba», но не соответствуют строки «ababa», «abcaaba», «codeforces», «aba1aba», «aba?aba».

Если строка \(t\) из соответствует шаблону \(s\), выведите «YES», иначе выведите «NO».

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

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

Прежде чем приступать к самой лепке, Гриша может несколько раз (\(0\) или более) изменить порядок кусочков следующим образом: произвольно разрезать последовательность полосок на две части, развернуть каждую из частей и затем склеить их вновь. К примеру, если у Гриши были полоски в порядке «bwbbw» (здесь «b» означает черную полоску, а «w» — белую), то можно было бы разрезать последовательность как bw|bbw (черта обозначает место разреза), перевернуть и получить «wbwbb» после склеивания.

Помогите Грише найти максимально возможную длину зебры.

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

Для каждой позиции \(i\) (\(1 \le i \le n\)) в строке \(s\) вам необходимо заменить букву на этой позиции либо на предыдущую в алфавитном порядке, либо на следующую (для букв 'a' и 'z' доступен только один вариант). Буква на каждой позиции должна быть изменена ровно один раз.

Например, буква 'p' должна быть изменена либо на 'o', либо на 'q', буква 'a' должна быть изменена на 'b', и буква 'z' должна быть изменена на 'y'.

Таким образом, строка «codeforces», например, может быть изменена на «dpedepqbft» ('c' \(\rightarrow\) 'd', 'o' \(\rightarrow\) 'p', 'd' \(\rightarrow\) 'e', 'e' \(\rightarrow\) 'd', 'f' \(\rightarrow\) 'e', 'o' \(\rightarrow\) 'p', 'r' \(\rightarrow\) 'q', 'c' \(\rightarrow\) 'b', 'e' \(\rightarrow\) 'f', 's' \(\rightarrow\) 't').

Строка \(s\) называется палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строки «abba» и «zz» — палиндромы, а строки «abca» и «zy» — нет.

Ваша задача — проверить, что можно сделать строку \(s\) палиндромом, применив выше приведенные замены к каждой позиции. Выведите «YES», если строку \(s\) можно сделать палиндромом. В противном случае выведите «NO».

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

Рассмотрим таблицу размера \(n \times m\) клеток, изначально полностью белую. Строки нумеруются от \(1\) до \(n\) сверху вниз, а столбы от \(1\) до \(m\) слева направо. Некоторый квадрат со стороной нечётной длины был покрашен в чёрный цвет. Найдите центр этого квадрата.

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

Определим подстроку какой-либо строки \(s\) с индексами от \(l\) до \(r\) как \(s[l \dots r]\).

Ваша задача — составить такую строку \(s\) минимальной возможной длины, что в ней существует ровно \(k\) позиций \(i\) таких, что \(s[i \dots i + n - 1] = t\). Другими словами, ваша задача — составить такую строку \(s\) минимальной возможной длины, что ровно \(k\) подстрок строки \(s\) равны \(t\).

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

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

Тест состоит из n вопросов, отвечать на них необходимо строго по порядку: с 1-го до n-го. В i-ом вопросе a_i вариантов ответа, ровно один из которых является верным.

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

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

Недавно Вася нашел золотой билет — последовательность из \(n\) цифр \(a_1a_2\dots a_n\). Вася считает билет счастливым, если его можно разбить на два или более непересекающихся отрезка с одинаковой суммой цифр на каждом отрезке. Например, билет \(350178\) счастливый, т. к. его можно разбить на три отрезка \(350\), \(17\) и \(8\): \(3+5+0=1+7=8\). Заметим, что каждая цифра должна принадлежать ровно одному отрезку.

Помогите Васе! Сообщите ему, является ли найденный им золотой билет счастливым.

В этой задаче мы рассматриваем упрощённую модель города Барселона.

Барселона может быть представлена как плоскость, а её улицы — как прямые вида \(x = c\) и \(y = c\) для любого целого числа \(c\) (то есть, улицы представляют собой прямоугольную сетку). Однако есть кое-что, что отличает Барселону от Манхеттена, а именно, проспект, который называется Avinguda Diagonal (Диагональный проспект) и который может быть представлен на плоскости как множество точек \((x, y)\), удовлетворяющих \(ax + by + c = 0\).

Перемещаться по городу можно только по улицам, в том числе и по Диагональному проспекту. Вам даны точки \(A\) и \(B\) в Барселоне. Найдите минимальное расстояние, которое необходимо пройти, чтобы попасть в точку \(B\) из точки \(A\).

Вам дана строка \(s\) длины \(n\), которая содержит только первые \(k\) букв латинского алфавита. Все буквы в строке \(s\) заглавные.

Строка называется подпоследовательностью строки \(s\), если она получается удалением из \(s\) нескольких символов без изменения порядка остальных символов. Например, «ADE» и «BD» являются подпоследовательностями «ABCDE», а «DEA» — нет.

Подпоследовательность \(s\) называется хорошей, если каждая из первых \(k\) букв алфавита встречается одинаковое число раз.

Найдите длину самой длинной хорошей подпоследовательности \(s\).

Дождливым пасмурным вечером, когда все модули попрятались по ближайшим кафетериям, попивая горячие энергококтейли, вирус Хексадесимал решила пролететь над Мэйнфреймом в поисках Гениальной Идеи. И Гениальная Идея нашлась!

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

В Мэйнфрейме в блэкджек играют стандартной колодой из 52-х карт, содержащей 13 значений — 2, 3, 4, 5, 6, 7, 8, 9, 10, валеты, дамы, короли, тузы — каждой из четырех мастей — черви, бубны, трефы и пики. Значения очков каждой карты: от двойки до десятки — соответственно от 2 до 10, у туза — 1 или 11 по желанию игрока, у картинок (король, дама, валет) — 10. Значение очков карты не зависит от масти. Правила игры предельно просты. Игрок получает две карты, если сумма очков этих карт равна n, то игрок победил, иначе — проиграл.

Игрок уже получил первую карту — это дама пик. Чтобы оценить шансы на победу, нужно определить, сколько существует способов получить вторую карту так, чтобы сумма очков была равна именно n.

В берляндском парке есть \(n\) лавочек. Про каждую лавочку известно количество людей \(a_i\), которые уже сидят на \(i\)-й лавочке. Известно, что в ближайшее время в парк придут ещё \(m\) человек, каждый из которых сядет на одну из \(n\) лавочек.

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

Считайте, что никто из посетителей парка не будет вставать с лавочек.

Аурук принимает участие в выборах в своей школе. Это последний раунд. У него есть ровно один оппонент — Элодрейп. В школе есть ровно \(n\) студентов. У каждого студента есть ровно \(k\) голосов и он обязан использовать их все. Тем самым, Аурук понимает, что если какой-то человек отдаёт \(a_i\) голосов за Элодрейпа, то ему достанется \(k - a_i\) голосов от этого человека. Конечно, должно выполняться \(0 \le k - a_i\).

Аурук знает, что если он проиграет, то его жизнь всё равно что кончится. Он поговорил со своими друзьями и теперь знает \(a_1, a_2, \dots, a_n\) — сколько голосов каждый школьник отдаст за Элодрейпа. Теперь он хочет поменять число \(k\), чтобы выиграть выборы. Он понимает, что чем больше \(k\), тем больше шансов, что кто-то заметит неладное, и что его дисквалифицируют.

Тем самым, Аурук знает \(a_1, a_2, \dots, a_n\) — сколько голосов каждый из школьников отдаст его оппоненту. Помогите ему выбрать наименьшее \(k\), которое приведёт к его выигрышу. Чтобы выиграть, Аурук должен набрать строго больше голосов, чем Элодрейп.

У IA есть невероятно много цветных магнитиков на её холодильнике. На каждом магнитике написана одна буква «a» или «b». Она любит играть с ними, располагая все магнитики в ряд. Однако девочка быстро устаёт и начинает думать, как сделать её развлечение ещё более интересным.

Сегодня, когда IA взглянула на холодильник, она заметила, что слово, образованное магнитиками, выглядит достаточно сомнительно. «Пожалуй, будет гораздо лучше, если я поменяю некоторые из них местами, — думает она, — но как это сделать?». Через некоторое время к ней пришла неплохая идея. IA будет рассматривать все префиксы с длинами от \(1\) до длины всего слова и для каждого префикса будет выбирать, стоит ли его развернуть или оставить как есть. Она будет рассматривать префиксы в фиксированном порядке: начнет с кратчайшего и закончит самым длинным. Она хочет получить в итоге лексикографически минимальное возможное слово. Можете ли вы помочь ей, сказав, какие именно из префиксов следует развернуть?

Строка \(a\) лексикографически меньше строки \(b\), если и только если выполняется один из следующих пунктов:

• \(a\) — префикс \(b\), но \(a \ne b\);
• в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(b\).

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

Это оказалось отличной новостью для Алисы, чей дедушка начал майнить биткоин еще в 2013, и накопил достаточно много. К сожалению, когда вы платите за что-то в биткоинах, все могут видеть, какая сумма у вас находится на данном биткоин-кошельке.

Это испугало Алису, поэтому она решила разделить все имеющиеся у нее биткоины по нескольким кошелькам так, чтобы в каждом кошельке было не более чем \(x\) сатоши (1 биткоин = \(10^8\) сатоши). Она может бесплатно создавать новые кошельки и будет платить по \(f\) сатоши за перевод некоторого количества биткоинов на новый кошелек. Эта плата списывается с кошелька, с которого выполняется перевод. Вычислите для Алисы, сколько она должна заплатить за переводы, чтобы достичь своей цели.

Каждый предмет в игре имеет уровень. Чем выше уровень — тем более высокие базовые параметры имеет вещь. Мы будем рассматривать только следующие базовые параметры: атака (atk), защита (def) и сопротивления к различным воздействиям (res).

Каждая вещь принадлежит одному из классов. В данной задаче мы будем рассматривать только три таких класса: оружие (weapon), броня (armor), защитные сферы (orb).

Кроме того, внутри каждого предмета скрыт целый мир. С помощью путешествий в мир данного предмета можно повышать его уровень. Также в Мире Вещей можно захватывать так называемых резидентов.

Резиденты — это существа, которые живут внутри предметов. Каждый резидент дает некоторый бонус предмету, в котором он на данный момент находится. Мы будем рассматривать только резидентов типов: гладиатор (gladiator, увеличивает параметр atk предмета), часовой (sentry, увеличивает def) и целитель (physician, увеличивает res).

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

У Лахарла есть некоторое количество предметов. Он хочет перераспределить резидентов между предметами таким образом, чтобы затем выбрать себе оружие, броню и защитную сферу для экипировки. При этом параметр оружия atk должен получиться максимально возможным. Из всех экипировок с максимальным параметром оружия atk параметр брони def должен быть максимальным. Из всех таких экипировок следует выбрать ту, в которой параметр защитной сферы res максимален. Значения параметров def и res у оружия, atk и res у брони и atk и def у защитной сферы Лахарлу безразличны.

Найдите оптимальную экипировку, которую Лахарл может получить.

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

Но так как EatForces заботится о безопасности своих пользователей, пароли пользователей должны содержать минимум одну цифру, минимум одну заглавную латинскую букву и минимум одну строчную латинскую букву. Например пароли «abaCABA12», «Z7q» и «3R24m» допустимы, а пароли «qwerty», «qwerty12345» и «Password» — нет.

Подстрока строки \(s\) — строка \(x = s_l s_{l + 1} \dots s_{l + len - 1} (1 \le l \le |s|, 0 \le len \le |s| - l + 1)\). \(len\) — длина подстроки. Обратите внимание, что пустая строка так же считается подстрокой строки \(s\), и имеет длину \(0\).

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

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

Маша живет в многоэтажном доме, у которого этажи пронумерованы натуральными числами. Два этажа называются соседними, если их номера — соседние натуральные числа. Маша решила сходить в гости к Егору. Маша живет на этаже с номером \(x\), Егор на этаже с номером \(y\) (не совпадающим с этажом Маши).

В доме есть лестница и работает лифт. Если Маша идет по лестнице, то она проходит между соседними этажами (в любую сторону) за \(t_1\) секунд. Лифт проезжает между соседними этажами (в любую сторону) за \(t_2\) секунд. Лифт передвигается с закрытыми дверьми. Чтобы открыть или закрыть двери, лифт тратит \(t_3\) секунд. Можно считать, что время не тратится ни на какие действия, кроме перемещения между соседними этажами и ожидания открытия или закрытия дверей. Если Маша вызовет лифт, то он тут же поедет к нужному этажу напрямую.

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

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

Помогите Маше понять: ехать на лифте или идти по лестнице.

В детском саду в группе \(n\) детей, пронумерованных от \(1\) до \(n\). Воспитательница дала \(i\)-му ребенку \(a_i\) (\(1 \leq a_i \leq n\)) конфет. Дети сели в ряд в порядке от \(1\) до \(n\) слева направо и стали есть конфеты.

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

Формально, \(l_i\) есть количество индексов \(j\) (\(1 \leq j < i\)), таких что \(a_i < a_j\), а \(r_i\) есть количество индексов \(j\) (\(i < j \leq n\)), таких что \(a_i < a_j\).

Каждый ребенок сказал воспитательнице посчитанные им числа \(l_i\) и \(r_i\). К сожалению, она уже забыла, сколько конфет кому она дала. Поэтому она просит помощи у вас — по массивам \(l\) и \(r\) определите, могла ли она дать детям конфеты так, что дети правильно посчитали свои значения \(l_i\) и \(r_i\), или кто-то из ребят точно ошибся, и она не могла так раздать конфеты. Если она могла раздать конфеты, то определите любой возможный способ того, как она могла это сделать.

Егор придумал новую головоломку из фишек, в которую предлагает сыграть вам.

Головоломка имеет вид таблицы из \(n\) строк и \(m\) столбцов, в каждой клетке которой могут располагаться несколько черных и белых фишек, положенных в ряд. Таким образом, состояние в клетке можно описать строкой, состоящей из символов «0» (белая фишка) и «1» (черная фишка), возможно пустой, а вся головоломка — это таблица, в каждой клетке которой стоит строка из нулей и единиц. Задача состоит в том, чтобы из одного состояния таблицы получить другое.

Для этого можно использовать следующую операцию:

• выбрать две различные клетки \((x_1, y_1)\) и \((x_2, y_2)\), при этом клетки должны находиться в одной строке или одном столбце таблицы, и строка в клетке \((x_1, y_1)\) должна быть непустой;
• за операцию можно переместить последний символ строки в клетке \((x_1, y_1)\) в начало строки в клетке \((x_2, y_2)\).

Для вас Егор загадал 2 состояния таблицы — начальное и конечное. Гарантируется, что количества нулей и единиц в таблицах совпадают. Ваша задача — с помощью нескольких операций получить из начального состояния конечное. Конечно, Егор не хочет, чтобы количество операций было очень большим. Обозначим за \(s\) количество символов в каждой из таблиц (в таблицах поровну символов). Тогда вы должны использовать не более \(4 \cdot s\) операций.

Алиса написала программу, и теперь всячески работает над улучшением её читаемости. Один из способов улучшить читаемость — давать переменным подходящие имена, поэтому Алиса хочет переименовать часть переменных в своей программе. В её среде разработке есть команда под названием «масштабный рефакторинг», которая позволяет менять сразу имена многим переменным. Для этого нужно выбрать две строки \(s\) и \(t\), после чего для всех переменных выполняется следующий алгоритм: если название переменной содержит \(s\) как подстроку, то первое (и только первое) вхождение \(s\) заменяется на \(t\), а если не содержит \(s\), то оно остаётся прежним.

Дан список переменных, для каждой из которых известно её исходное название и название, на которое Алиса хочет его заменить. Известно, что у каждой переменной длины этих двух названий совпадают (это связано с тем, что выравнивание блоков может «поехать», если длины названий переменных изменятся). Требуется произвести переименование всех переменных за ровно один вызов команды масштабного рефакторинга, или сказать, что это невозможно сделать.

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

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

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

Это — интерактивная задача. Вам нужно написать программу, которая будет оптимально выбирать героев в одну команду, в то время как программа жюри будет играть за другую команду. Обратите внимание, что программа жюри может играть не оптимально, в таком случае вам необходимо использовать шанс и все равно максимизировать суммарную силу своей команды. Формально, если в какой-то момент у вас есть возможность набрать суммарную силу героев в \(q\) или больше, независимо от дальнейших ходов программы жюри, вы должны набрать \(q\) или больше для того, чтобы пройти тест.

Когда очередь ходить ваша, выведите одно целое число \(x\) (\(1 \le x \le 2n\)) — индекс героя, которого вы выбираете. Обратите внимание, вы не можете выбрать героя, которого ранее выбрали вы либо другой игрок, и вы должны следовать правилу о специальных парах героев.

Когда очередь ходить вашему сопернику, считайте одно целое число \(x\) (\(1 \le x \le 2n\)) — индекс героя, выбранного другой командой. Гарантируется, что выбранный герой не будет выбран ранее; гарантируется, что соперник будет следовать правилу о специальных парах героев.

После последнего хода вы должны завершиться, не выводя ничего.

После вывода хода не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

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

Студент Андрей весь семестр пропускал физкультуру в своем университете, и вот теперь настала пора получать по ней зачет. Разумеется, получить зачет честно Андрей не успевает, но он не сдается. Добыв в местной поликлинике пустой бланк справки, Андрей, зная почерк местного врача, решил подделать справку о болезни. И вот, когда большая часть уже написана, Андрей с ужасом понял, что подпись врача подделать невозможно. Или возможно?

Для удобства Андрей мысленно представил подпись как клетчатое поле \(n\times m\), где каждая клетка либо заполнена чернилами, либо пуста. Ручка Андрея заполняет чернилами квадрат \(3\times3\) без центральной клетки, если он полностью лежит внутри поля, как показано ниже.

xxx
x.x
xxx

Определите, может ли Андрей нарисовать подпись врача на пустом листе бумаги \(n\times m\).

Вася выбирает ноутбук. В магазине имеется n ноутбуков на самый разный вкус.

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

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

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

Даны два массива \(a\) и \(b\) из целых положительных чисел, длины \(n\) и \(m\) соответственно.

Рассмотрим матрицу \(c\) размера \(n \times m\), где \(c_{i,j} = a_i \cdot b_j\).

Вам необходимо найти в матрице \(c\) подпрямоугольник максимальной площади, сумма чисел в котором не превосходит \(x\).

Формально, необходимо найти такую максимальную площадь \(s\), что существуют четыре целых числа \(x_1, x_2, y_1, y_2\), удовлетворяющих ограничениям \(1 \leq x_1 \leq x_2 \leq n\), \(1 \leq y_1 \leq y_2 \leq m\), \((x_2 - x_1 + 1) \times (y_2 - y_1 + 1) = s\), таких что \(\)\sum_{i=x_1}^{x_2}{\sum_{j=y_1}^{y_2}{c_{i,j}}} \leq x.\(\)

Вы пришли на выставку и один экспонат привлёк ваше внимание. Он состоит из \(n\) колонн, где \(i\)-я колонна состоит из \(a_i\) блоков стоящих на полу.

Высота экспоната равна \(m\), а значит количество блоков в каждой колонне не превосходит \(m\).

На потолке есть камера, которая снимает вид экспонат сверху, а также ещё одна камера расположена сбоку и снимает боковой вид этого экспоната.

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

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

Есть \(n\) телепередач, которые вы хотите посмотреть. Предположим, что всё время разбито на равные отрезки называемые «минутами». Тогда \(i\)-я телепередача идёт с \(l_i\)-й по \(r_i\)-ю минуту, оба конца включительно.

Конечно, чтобы посмотреть телепередачу нужен телевизор, а также нельзя смотреть две телепередачи идущие одновременно на одном телевизоре. Из-за этого, возможно, в некоторые минуты вам понадобится более одного телевизора. В частности, если отрезки \([l_i, r_i]\) и \([l_j, r_j]\) пересекаются, то телепередачи \(i\) и \(j\) нельзя смотреть одновременно на одном телевизоре.

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

К счастью, рядом с вами есть магазин по аренде телевизоров. Он сдаёт телевизор в аренду за \(x\) рупий и взимает \(y\) (\(y < x\)) рупий за каждую следующую минуту, в течении которой вы держите телевизор у себя. В частности, чтобы арендовать один телевизор на время \([a; b]\) нужно заплатить \(x + y \cdot (b - a)\) рупий.

Считайте, что аренда и возврат телевизора не занимает времени и не отвлекает от просмотра других телепередач. Выясните минимальное возможное количество денег, которое нужно заплатить, чтобы посмотреть все телепередачи. Так как это значение может быть достаточно велико, выведите его по модулю \(10^9 + 7\).

JATC любит Бань-ми (вьетнамское блюдо). Его привязанность к Бань-ми настолько велика, что он ест Бань-ми каждый день на завтрак. Сегодня утром, как обычно, он купил Бань-ми, но собирается насладиться им необычным образом.

Сначала, он разбивает Бань-ми на \(n\) кусочков, выкладывает их в ряд и нумерует от \(1\) до \(n\). Для каждого кусочка \(i\) он определяет его вкусность как \(x_i \in \{0, 1\}\). JATC собирается съесть все кусочки один за другим. Каждый раз он выбирает произвольный из оставшихся кусочков и съедает его. Пусть этот кусочек был под номером \(i\), тогда его удовольствие от Бань-ми увеличивается на \(x_i\), вкусность каждого из оставшихся кусочков также увеличивается на \(x_i\). Изначально удовольствие JATC равно \(0\).

Например, пусть есть \(3\) кусочка с вкусностями \([0, 1, 0]\). Если JATC съест второй кусочек, то его удовольствие станет равно \(1\), а вкусность оставшихся кусочков будет равна \([1, \_, 1]\). Затем, если он съест первый кусочек, то его удовольствие станет равна \(2\), а вкусность оставшихся кусочков станет \([\_, \_, 2]\). После того как JATC съест последний кусочек, его удовольствие станет равно \(4\).

Однако JATC не хочет съесть сразу все кусочки, оставив часть на будущее. Он дал вам \(q\) запросов, каждый из которых задаётся двумя целыми числам \(l_i\) и \(r_i\). Для каждого запроса выясните какое наибольшее удовольствие он может получить, если съест все кусочки в отрезке \([l_i, r_i]\) в каком-то порядке.

Все запросы независимы друг от друга. Так как ответ на запрос может быть очень большим, выведите его по модулю \(10^9+7\).

В любимом Васином магазине началась акция: купи \(a\) шоколадок и \(b\) получи в подарок! Один и тот же клиент может воспользоваться этим акционным предложением неограниченное количество раз.

За время каникул Вася накопил \(s\) рублей, и он хочет купить на них максимально возможно количество шоколадок. Зная, что каждая шоколадка стоит \(c\) рублей, сообщите Васе, какое максимальное количество шоколадок он может получить!

У Максима есть \(n\) предметов и \(m\) коробок, каждая коробка имеет размер \(k\). Предметы пронумерованы от \(1\) до \(n\) в порядке слева направо, размер \(i\)-го предмета равен \(a_i\).

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

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

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

Polycarp is an introvert person. In fact he is so much of an introvert that he plays "Monsters and Potions" board game alone. The board of the game is a row of \(n\) cells. The cells are numbered from \(1\) to \(n\) from left to right. There are three types of cells: a cell containing a single monster, a cell containing a single potion or a blank cell (it contains neither a monster nor a potion).

Polycarp has \(m\) tokens representing heroes fighting monsters, which are initially located in the blank cells \(s_1, s_2, \dots, s_m\). Polycarp's task is to choose a single cell (rally point) and one by one move all the heroes into this cell. A rally point can be a cell of any of three types.

After Policarp selects a rally point, he picks a hero and orders him to move directly to the point. Once that hero reaches the point, Polycarp picks another hero and orders him also to go to the point. And so forth, until all the heroes reach the rally point cell. While going to the point, a hero can not deviate from the direct route or take a step back. A hero just moves cell by cell in the direction of the point until he reaches it. It is possible that multiple heroes are simultaneously in the same cell.

Initially the \(i\)-th hero has \(h_i\) hit points (HP). Monsters also have HP, different monsters might have different HP. And potions also have HP, different potions might have different HP.

If a hero steps into a cell which is blank (i.e. doesn't contain a monster/potion), hero's HP does not change.

If a hero steps into a cell containing a monster, then the hero and the monster fight. If monster's HP is strictly higher than hero's HP, then the monster wins and Polycarp loses the whole game. If hero's HP is greater or equal to monster's HP, then the hero wins and monster's HP is subtracted from hero's HP. I.e. the hero survives if his HP drops to zero, but dies (and Polycarp looses) if his HP becomes negative due to a fight. If a hero wins a fight with a monster, then the monster disappears, and the cell becomes blank.

If a hero steps into a cell containing a potion, then the hero drinks the potion immediately. As a result, potion's HP is added to hero's HP, the potion disappears, and the cell becomes blank.

Obviously, Polycarp wants to win the game. It means that he must choose such rally point and the order in which heroes move, that every hero reaches the rally point and survives. I.e. Polycarp loses if a hero reaches rally point but is killed by a monster at the same time. Polycarp can use any of \(n\) cells as a rally point — initially it can contain a monster, a potion, or be a blank cell with or without a hero in it.

Help Polycarp write a program to choose a rally point and the order in which heroes move.

Polycarp took \(n\) videos, the duration of the \(i\)-th video is \(a_i\) seconds. The videos are listed in the chronological order, i.e. the \(1\)-st video is the earliest, the \(2\)-nd video is the next, ..., the \(n\)-th video is the last.

Now Polycarp wants to publish exactly \(k\) (\(1 \le k \le n\)) posts in Instabram. Each video should be a part of a single post. The posts should preserve the chronological order, it means that the first post should contain one or more of the earliest videos, the second post should contain a block (one or more videos) going next and so on. In other words, if the number of videos in the \(j\)-th post is \(s_j\) then:

• \(s_1+s_2+\dots+s_k=n\) (\(s_i>0\)),
• the first post contains the videos: \(1, 2, \dots, s_1\);
• the second post contains the videos: \(s_1+1, s_1+2, \dots, s_1+s_2\);
• the third post contains the videos: \(s_1+s_2+1, s_1+s_2+2, \dots, s_1+s_2+s_3\);
• ...
• the \(k\)-th post contains videos: \(n-s_k+1,n-s_k+2,\dots,n\).

Polycarp is a perfectionist, he wants the total duration of videos in each post to be the same.

Help Polycarp to find such positive integer values \(s_1, s_2, \dots, s_k\) that satisfy all the conditions above.

У Васи есть \(n\) книг, пронумерованных от \(1\) до \(n\), сложенных в стопку. Самая верхняя книга имеет номер \(a_1\), следующая за ней имеет номер \(a_2\), и так далее. Самая нижняя книга имеет номер \(a_n\). Все книги имеют различные номера.

Вася хочет переложить все книги в рюкзак за \(n\) шагов. На \(i\)-м шаге он хочет переложить в рюкзак книгу с номером \(b_i\). Если книга с номером \(b_i\) есть в стопке — он перекладывает эту книгу и все книги, лежащие над книгой \(b_i\), иначе переходит к следующему шагу. Например, если книги лежат в порядке \([1, 2, 3]\) (книга \(1\) лежит наверху), а Вася перекладывает книги в порядке \([2, 1, 3]\), то на первом шаге он переложит две книги (с номерами \(1\) и \(2\)), на втором — ни одной (так как книги \(1\) уже нет в стопке), а на третьем — одну (с номером \(3\)). Обратите внимание, что числа \(b_1, b_2, \dots, b_n\) различны.

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

Пало-Алто — необычный город, ведь он представляет собой бесконечную координатную прямую. Он известен еще тем, что там находится офис Lyft Level 5.

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

Каждый житель (включая таксистов) Пало-Алто живёт в точке с уникальной координатой (нет такой пары жителей, что их координата одинаковая).

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

Однажды утром таксистам стало интересно: а сколько же есть людей, от которых они могут получить первый вызов в этот день? Другими словами, надо для каждого таксиста \(i\) найти число \(a_{i}\) — количество пешеходов, для которых \(i\)-й таксист — ближайший, или, если таких таксистов несколько, имеет среди таковых наименьшую координату.

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

Таттах спит тогда и только тогда, когда он на лекции. Эта шутка популярна среди его однокурсников.

В среду утром Таттах был на лекции у профессора NN. В 12:21, как раз перед сном, он созерцал часы на запястье Захира. Таттах обратил внимание, что цифры на часах обозначали одно и то же время будучи прочитанными как справа налево (*), так и слева направо. Иными словами, время на часах было палиндромом.

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

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

(*) Как и все египтяне, Таттах читает справа налево.