Информатика

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

Все квесты в игре имеют одинаковую структуру. Пусть на карте расположены \(m\) комнат. Тогда каждый квест задаётся парой комнат \(u\) и \(v\) (\(1 \le u \le v \le m\)). Для прохождения этого квеста игроку нужно переместиться из комнаты \(u\) в комнату \(v\). Для усложнения игры в каждой комнате, через которую пройдёт игрок (включая начальную и конечную комнату) необходимо решить загадку. Влад называет сложностью квеста минимальное количество загадок, которые надо решить, чтобы его пройти. В частности, сложность квеста, у которого начальная и конечная комната совпадает, равна \(1\), а сложность квеста, в котором начальная и конечная комнаты соединены коридором равна \(2\). Также Влад называет квест трудным, если не существует квеста с большей сложностью, чем данный.

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

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

Формат выходных данных
В первой строке выведите целое число \(m\) — минимальное количество комнат на карте.

В следующих \(m - 1\) строках выведите через пробел пары целых чисел \(u\) и \(v\), обозначающие коридор, между комнатами \(u\) и \(v\).

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

Примечание
В первом примере карта выглядит так:

На этой карте есть 10 квестов. Обозначим за (u, v) квест, который начинается в комнате с номером u и заканчивается в комнате с номером v. Сложность квестов (1, 1), (2, 2), (3, 3) и (4, 4) равна 1, сложность квестов (1, 2), (1, 3) и (1, 4) равна 2, а сложность квестов (2, 3), (2, 4) и (3, 4) равна 3. Таким образом, трудными квестами являются квесты (2, 3), (2, 4) и (3, 4). Трудных квестов 3, значит интересность игры на данной карте равна 3.

Во втором тестовом примере карта выглядит так:

На этой карте есть 4 трудных квеста (2, 5), (2, 6), (3, 5) и (3, 6). Их сложность равна 4.

В третьем тестовом примере карта выглядит так:

На этой карте есть 5 трудных квестов (2, 8), (3, 8), (4, 8), (5, 8), (6, 8) со сложностью 4.

Квартира Максима еще не прошла реновацию, поэтому температура в ней сильно зависит от температуры на улице. Для поддержания комфортной температуры он купил обогреватель и установил систему <<Умный дом>>. В соответствующую программу Максим заложил два целых числа \(t_{min} \leq t_{max}\) и следующий алгоритм использования обогревателя:

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

2. Если в течение последних пяти дней до текущего дня включительно обогреватель каждый день был включен, и в каждый из этих дней температура на улице была строго больше \(t_{max}\), то надо выключить обогреватель в этот день и считать, что он был выключен весь день. Обогреватель остается выключенным и в последующие дни до тех пор, пока программа его не включит.

Из-за кратковременного отключения электроэнергии программу необходимо настроить заново. Сами значения \(t_{min}\) и \(t_{max}\) Максим забыл, зато у него остались записи программы о температуре и состоянии обогревателя в каждые из \(n\) дней использования системы.

Максим помнит, что \(t_{min}\) и \(t_{max}\) были целыми числами, по модулю не превосходящими \(10^9\) и \(t_{min} \leq t_{max}\), также он помнит, что программа не учитывала дни до первого дня использования системы и не включала обогреватель в течение первых четырех дней. Наконец, Максим помнит, что он выбирал \(t_{min}\) и \(t_{max}\) как можно более близкими друг к другу.

Помогите найти два подходящих значения \(t_{min}\) и \(t_{max}\), не превосходящих \(10^9\) по абсолютной величине, таких, что выполняются правила использования обогревателя в каждые из \(n\) дней, \(t_{min}\) не превосходит \(t_{max}\) и величина \(t_{max} - t_{min}\) минимальна.

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

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

Во второй строке входных данных задаются \(n\) целых чисел \(t_1, \dots, t_n\) (\(-10^9 \leq t_i \leq 10^9\)) — температуры на улице в каждый из \(n\) дней.

В третьей строке входных данных задается строка из \(n\) символов, состоящая из 0 и 1 — если в \(i\)-й позиции данной строки записан 0, то это значит, что в \(i\)-й день обогреватель был выключен, а если 1, — то включен.

Формат выходных данных
В единственной строке выведите два целых числа \(t_{min}\) и \(t_{max}\) (\(t_{min} \leq t_{max}\)), по модулю не превосходящих \(10^9\) — значения температур, при вставке которых в программу обогреватель будет включен и выключен в те же дни, в которые он был включен и выключен при исходных значениях, а значение \(t_{max} - t_{min}\) минимально.

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

В первом тестовом примере первые пять дней температура строго меньше \(7\) градусов, при этом до пятого дня обогреватель был в каждый из четырех дней выключен, следовательно в пятый день программа его включила. На данный тест корректен любой ответ удовлетворяющий условию \(6 \leq t_{min} = t_{max} \leq 10^9\).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вадим работает в ЖКХ и сегодня он крайне озабочен вопросов сосулек. А именно он наблюдает за домом по адресу — проспект Программистов, дом 404. В доме \(n\) этажей, на каждом этаже по \(m\) окон, включая первый. Окна на каждом этаже пронумерованы слева направо от \(1\) до \(m\). \(i\)-e окно \(j\)-го этажа находится ровно под \(i\)-м окном \(j + 1\)-го этажа. Под некоторыми окнами свисают сосульки.

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

Помогите Вадиму выбрать нужное окно.

Формат входных данных
В первой строке содержатся числа \(n\), \(m\), \(d\), \(k\) — количество этажей, количество окон на каждом этаже, длина козырька и количество окон, под которыми есть сосульки, соответственно (\(1 \le n, m \le 100\),\(1 \le d \le m\), \(0 \le k \le n \cdot m\)).

В следующих \(k\) строках заданы тройки чисел \(x\), \(y\), \(z\) — номер этажа, номер окна на этаже и количество сосулек под ним (\(1 \le x \le n\), \(1 \le y \le m\), \(1 \le z \le 10\)).

Гарантируется, что каждая пара \(x\), \(y\) встречается не более одного раза.

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

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

Во втором примере козырек имеет длину один и если его поставить под окнами с номерами \(1\), \(2\) или \(3\), над ним будет соответственно \(0\), \(1\) или \(1\) сосулька. Таким образом подходит две позиции начала козырька, выбираем более левую.

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

Однажды, девочка Аня записала несколько целых чисел лежащих в диапазоне от \(-1000\) до \(1000\) в некоторую изначально пустую строку \(S\), разделив каждые два пробелом. Но стоило ей отвернуться, как злой хулиган Гриша заменил все пробелы в строке на подстроки из строчных латинских букв. Тем не менее и этого ему показалось мало, поэтому он мог дописать латинских строчных букв еще и в начало и конец строки \(S\).

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

Формат входных данных
В первой строке содержится одно натуральное число \(n\) — количество символов в строке \(S\) (\(1 \le n \le 100\)).

Во второй строке содержится строка \(S\), состоящая из латинских строчных букв, цифр и знаков <<->>.

Гарантируется:

• В данной строке содержится хотя бы одна цифра

• В следующей позиции после каждого знака <<->> находится цифра

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

Формат выходных данных
В единственной строке выведите наибольшее число, которое было у Ани в строке.

Обратите внимание, что \(0\) следует выводить без знака <<->>.

Алина выписала на доске \(n + 1\) цифру, каждая из которых от \(1\) до \(9\). Даша поставила между каждой парой соседних цифр знак одной из арифметических операций <<+>>, <<->>, <<*>> и <</>> (плюс, минус, умножить, целочисленное деление). Затем девочки отправились в столовую на обед.

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

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

Формат входных данных
В первой строке входного файла дано число \(n\), число знаков, которые написала Даша (\(1 \le n \le 1000\)).

Во второй строке находится \(n\) знаков арифметических операций <<+>>, <<->>, <<*>> и <</>> (без кавычек).

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

Если возможных решений несколько, разрешается вывести любое.

Федок очень хочет купить себе комплексный обед в столовой, но сделать это не так просто. В столовой работает всего одна касса, и то очень медленно. На данный момент в очереди находится \(n\) \((2 \leq n \leq 100\,000)\) людей, а сам Федок находится на \(k-\)ой \((1 \leq k \leq n)\) позиции в ней. И вот, чтобы занять себя в этой очереди, Федок стал обдумывать коварный план как побыстрее оплатить комплексный обед и начать есть.

В чем состоит коварный план? Федок хочет крикнуть, что открылась новая касса. Тогда, по его мнению, многие уйдут из очереди в поисках этой кассы, а он приблизится к заветной еде. Но вот в чем проблема: не все люди так нетерпеливы как наш герой. Проще говоря, у каждого человека есть свой параметр \(P_i\) — терпеливость. Если человек стоит на позиции \(x\) и его терпеливость равна \(y\), то он уйдет искать новую кассу только в том случае, если \(y < x\)

Казалось бы, эта задача трудна, но и Федок не глуп. Он своим метким взором определил терпеливости всех людей, стоящих в очереди кроме него. Увы, так как людей очень много, в его голове все перепуталось, и некоторые числа поменялись местами. Таким образом наш герой получил некоторую перестановку множества терпеливости всех людей в очереди \(P_1, P_2, \ldots, P_{n-1}\)

Федок не знает точно, кто насколько терпелив и боится, что не сдвинется в очереди после реализации своей задумки. Поэтому он просит вас помочь ему узнать, какую минимальную и максимальную позицию от начала очереди он может занимать после того как крикнет: <<Свободная касса!>>

Формат входных данных
В первой строке входных данных находится число людей в очереди \(n\) (\(2 \leq n \leq 100\,000\))

Во второй строке находится число \(k\) (\(1 \leq k \leq n\)) — текущая позиция Федка в очереди

В следующей строке содержатся \(n-1\) число — перестановка множества терпеливостей людей в очереди \((0 \leq P_i \leq n)\)

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

Во второй строке выведите максимальное место, которое может стать у Федка после применения его плана

• Решения, работающие для \(n \leq 10\) будут набирать не менее 5 баллов

• Решения, работающие для \(n \leq 1000\) будут набирать не менее 10 баллов

Пояснение к первому тесту:

Алексей стоит на второй позиции. Перед ним один человек.

Если его терпеливость будет равна нулю, то он уйдет, и Федок станет первым

Если же его терпеливость равна трем, то он не уйдет, и Федок останется второй

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

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

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

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

Замечание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Замечание

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

Поле в игре <<Речной бой>> представляет собой полоску длины \(n\) клеток и шириной в одну клетку. Где-то на поле расположен корабль из \(k\) клеток (\(k \le n\)). Какое наименьшее число выстрелов необходимо, чтобы гарантированно потопить корабль? После каждого выстрела сообщается его результат: <<мимо>>, <<ранен>> или <<убит>>.

Формат входных данных
Первая строка входных данных содержит целое число \(n\) (\(1 \le n \le 10^9\)).

Вторая строка входных данных содержит целое число \(k\) (\(1 \le k \le n\)).

Формат выходных данных
Выведите одно целое число — количество выстрелов.

Замечание

В первом примере поле состоит из \(n=4\) клеток, корабль имеет длину \(k=2\). Первый выстрел нужно сделать в одну из двух центральных клеток. Если результатом будет <<ранен>>, то вторая клетка корабля находится в одной из двух соседних клеток, и за два выстрела мы гарантированно потопим корабль Если результатом первого выстрела будет <<мимо>>, то корабль занимает две единственные свободные смежные клетки, которые тоже можно подбить двумя выстрелами. Итого нужно 3 выстрела. Двух выстрелов недостаточно, так как всегда есть шанс промахнуться первым выстрелом.

У Алисы сегодня день рождения, и она хочет угостить своих одноклассников конфетами. В магазине, в который она успеет зайти перед школой, есть сладости двух видов: шоколадные и карамельные. Они продаются наборами по 3 штуки, причем в упаковке есть конфеты каждого из двух видов (то есть в одной упаковке лежат две конфеты одного вида и одна конфета другого вида). По внешнему виду упаковки нельзя понять, какие конфеты лежат внутри.

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

Формат входных данных
В единственной строке задано число \(n\) (\(1 \le n \le 10 ^ 9\)) — количество человек в классе.

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

Выведите единственное число — количество упаковок, которое должна купить Алиса.

Замечание

В первом примере Алиса купит две упаковки с конфетами. В первой упаковке лежат 2 конфеты одного вида, и 1 конфета другого вида. Если вторая упаковка будет такая же, как и первая, то у Алисы окажется 4 конфеты одного вида и 2 конфеты другого вида. Если вторая упаковка будет отличаться от первой, то у Алисы будет по 3 конфеты каждого вида. В любом случае у Алисы найдётся 3 конфеты одного вида.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

 

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

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

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

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

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

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

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

Замечание

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

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

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

Формат входных данных
Три строки содержат три натуральных числа: \(n\) — количество домов на улице, \(a\) и \(b\) — выбранные Воробьяниновым числа. Все числа не превосходят \(10^9\).

Формат выходных данных
Выведите одно неотрицательное целое число — количество расклеенных афиш.

Замечание
В первом примере на улице \(10\) домов. Ипполит Матвеевич первым проходом расклеил пять афиш на дома, номера которых делятся на \(2\), то есть на дома с номерами \(2\), \(4\), \(6\), \(8\), \(10\). Вторым проходом он расклеил две афиши на дома, номера которых делятся на \(3\), то есть на дома с номерами \(3\) и \(9\). Дом номер \(6\) он пропустил — на нем афиша уже висит. Всего наклеено \(7\) афиш.

Во втором примере Воробьянинов не наклеит ни одной афиши.

Кай работает в лаборатории изучения массивов, он экспериментирует с двумя массивами натуральных чисел: \(A = [a_1, a_2, \ldots, a_n]\) длины \(n\) и \(B = [b_1, b_2, \ldots, b_m]\) длины \(m\).

Эксперимент, который проводит Кай, устроен следующим образом. У каждого из массивов отбрасывается произвольный, возможно пустой, префикс, а также произвольный, возможно пустой, суффикс, таким образом, чтобы оставшиеся части массивов имели равную длину. Обозначим получившиеся массивы как \(A'\) и \(B'\), а их длину как \(k\). Затем Кай суммирует поэлементно получившиеся массивы, итоговый массив Кай обозначает как \(C = [c_1, c_2, \ldots, c_k]\).

Пусть, например, \(n = 5\), \(A = [4, 3, 3, 2, 1]\), \(m = 6\), \(B = [4, 1, 5, 1, 3, 2]\), от массива \(A\) отбрасывается первый и последний элемент, от массива \(B\) три первых. После этого массивы имеют вид \(A' = [3, 3, 2]\), \(B' = [1, 3, 2]\), результат их поэлементного суммирования \(C = [4, 6, 4]\).

Задача Кая заключается в том, чтобы получать такие \(C\), которые являются массивами-палиндромами, то есть если числа на первой и последней позиции совпадают, числа на второй и предпоследней позиции совпадают, и так далее, для всех \(i\) числа на позициях \(i\) и \(k - i + 1\) совпадают.

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

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

Во второй строке ввода даны \(n\) целых чисел \(a_{i}\) — массив \(A\) (\(1 \leqslant a_i \leqslant 100\)).

В третьей строке ввода даны \(m\) целых чисел \(b_{j}\) — массив \(B\) (\(1 \leqslant b_j \leqslant 100\)).

Формат выходных данных
Выведите единственное целое число — максимальное \(k\), что Кай в результате эксперимента может получить массив-палиндром длины \(k\).

 

Председатель жюри чемпионата по устному счету Иван Владимирович Треугольников придумал новое задание для участников чемпионата. Исходно на доске выписывается \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\). После этого участник должен выполнять команды двух типов:

1. Стереть \(i\)-е число с доски и записать вместо него число \(x\). То есть, если на доске были записаны числа \(a_1, a_2, \ldots, a_n\), то после выполнения команды числа будут равны: \(a_1, \ldots, a_{i - 1}, x, a_{i + 1}, \ldots, a_n\).

2. Циклически сдвинуть последовательность чисел на \(k\) вправо. То есть, если на доске были записаны числа \(a_1, a_2, \ldots, a_n\), то после выполнения команды числа будут равны: \(a_{n - k + 1}, a_{n - k + 2}, \ldots, a_n, a_1, a_2, \ldots, a_{n - k}\).

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

Формат входных данных
В первой строке записано целое число \(n\) — количество чисел, изначально записанных на доске (\(2 \leq n \leq 10^5\)).

Во второй строке через пробел записаны \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\) — числа, изначально выписанные на доске (\(-10^9 \leq a_i \leq 10^9\)).

В третьей строке записано целое число \(q\) — количество команд, которые необходимо выполнить (\(1 \leq q \leq 10^5\)).

В каждой из следующих \(q\) строк записана очередная команда в следующем формате:

• \(1~i~x\) — это означает, что участник должен заменить \(i\)-е число последовательности на число \(x\) (\(1 \leq i \leq n\); \(-10^9 \leq x \leq 10^9\)).

• \(2~k\) — это означает, что участник должен циклически сдвинуть последовательность чисел на \(k\) вправо (\(1 \leq k < n\)).

Формат выходных данных
В качестве ответа выведите \(q\) строк, в каждой из которых записано одно целое число.

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

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

Замечание
Рассмотрим пример из условия. Изначально последовательность записанных на доске чисел равна: \(4,~1,~2,~1,~5,~3\).

После первой команды последовательность циклически сдвигается на \(3\) элемента вправо. Новая последовательность: \(1,~5,~3,~4,~1,~2\). Сумма чисел равна: \(1 + 5 + 3 + 4 + 1 + 2 = 16\).

После второй команды необходимо заменить третий элемент последовательности на число \(10\). Новая последовательность: \(1,~5,~10,~4,~1,~2\). Сумма чисел равна: \(1 + 5 + 10 + 4 + 1 + 2 = 23\).

После третьей команды заменить четвертый элемент на число \(4\). Так как четвертый элемент уже равен \(4\), последовательность не изменяется. Сумма чисел также равна \(23\).

После четвертой команды последовательность циклически сдвигается на \(1\): \(2,~1,~5,~10,~4,~1\). Сумма чисел не изменилась.

Наконец, после пятой команды последовательность становится равна: \(-10,~1,~5,~10,~4,~1\). Сумма чисел в итоговой последовательности равна \(-10 + 1 + 5 + 10 + 4 + 1 = 11\).

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


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


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

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


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


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