Алина выписала на доске \(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.


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

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

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

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

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

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

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

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

Замечание

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

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

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

Текстовый файл состоит не более чем из 10⁷ символов и содержит только заглавные буквы A, B, C, D. Определите максимальную длину подстроки, состоящей из идущих групп символов ABCD в указанном порядке. При этом в начале и конце искомой последовательности группа символов ABCD может быть неполной. Искомая подстрока должна содержать не менее одной полной группы символов ABCD.

Например, условию задачи удовлетворяют: BCDABCDABCDA, DABCDABCDAB

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

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

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

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

На вас возложили ответственную задачу по управлением роботом-курьером. Карта, по которой перемещается робот, представляет из себя поле размера \(n \times m\) (\(n\) строк и \(m\) столбцов). Каждая клетка поля может быть либо тротуаром (‘.’), либо проезжей частью дороги (‘+’).

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

Робот может перемещаться только по тротуарам и пешеходным переходам. Для определения цвета светофора робот обладает камерой с разрешением \(h \times w\) (где \(w\) четно). Для управления роботом вы можете передавать ему следующие команды:

• <<turn \(c\)>>, где \(c \in \{\text{`{L}'}, \text{`{U}'}, \text{`{R}'}, \text{`{D}'}\}\), означает поворот в соответствующую сторону (влево, вверх, вправо или вниз);

• <<move>> означает перемещение на одну клетку вперед относительно текущего направления;

• <<camera>> означает получение изображения с камеры; в ответ на эту команду вы получаете таблицу из \(h \times w\) символов, каждый из которых описывает преобладающий цвет (‘r’, ‘g’ или ‘b’ — красный, зеленый или синий) в соответствующей области пространства перед роботом;

• <<wait \(t\)>> означает ожидание в течение \(t\) секунд.

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

Светофоры могут находиться на разной высоте и на разном расстоянии сбоку от соответствующего перехода. Если робот находится около перехода с \(i\)-м светофором и смотрит в его направлении, на изображении с камеры светофор будет занимать две клетки в \(a_i\)-й и \((a_i + 1)\)-й снизу строках в столбце на расстоянии \(b_i\) от центра (слева от центра, если \(b_i < 0\), и справа, если \(b_i > 0\)). Для светофора, горящего красным, нижняя из этих двух клеток равна ‘b’, а верхняя равна ‘r’. Для зеленого светофора нижняя клетка равна ‘g’, а верхняя — ‘b’. Остальные клетки на изображении могут любого из трех цветов.

Требуется переместить робота из клетки \((i_1, j_1)\) (\(i_1\)-я сверху строка, \(j_1\)-й слева столбец) в клетку \((i_2, j_2)\). Начинать пересекать пешеходные переходы можно только если на соответствующем светофоре горит зеленый сигнал. Если движение по переходу начато, когда на светофоре горит зеленый сигнал, можно считать, что как минимум в течение еще двух секунд находиться на переходе безопасно, то есть можно гарантированно переместиться на тротуар на противоположной стороне дороги.

Напишите программу, сообщающую роботу команды, безопасно приводящие его из стартовой клетки в конечную. Минимизировать затраченное в пути время не требуется. В изначальной клетке робот находится в направлении <<вверх>> (‘U’).

Каждый тест состоит из нескольких наборов входных данных. В первой строке ввода дано единственное целое число \(t\) — количество наборов входных данных в тесте (\(1 \le t \le 50\)).

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

В первой строке описания карты даны два целых числа \(n\) и \(m\) — размеры карты (\(1 \le n, m \le 50\)). Следующие \(n\) строк содержат по \(m\) символов каждая и описывают карту. Символ на \(j\)-й позиции \(i\)-й строки описывает клетку с координатами \((i, j)\) и равен ‘.’, если это клетка тротуара, и ‘+’, если это клетка проезжей части.

В следующей строке даны три целых числа \(k\), \(h\) и \(w\) — количество переходов со светофорами и разрешение камеры, соответственно (\(k \le n \cdot m\); \(2 \le h, w \le 8\); \(w\) четно).

Следующие \(3k\) строк описывают светофоры: по три на каждый из \(k\) переходов. В первой строке для \(i\)-го светофора дано положение соответствующего ему перехода \((r_i, c_i)\) (\(1 \le r_i \le n\); \(1 \le c_i \le m\)). Во второй строке дано описание светофора с одного из двух концов перехода в формате <<\(d_{i,1}\) \(a_{i,1}\) \(b_{i,2}\)>>, где \(d_1\) указывает на направление перехода, соответствующее этому светофору, а \(a_{i,1}\) и \(b_{i,1}\) — его высота и расстояние от центра перехода, соответственно (\(d_{i,1} \in \{\text{`{L}'}, \text{`{U}'}, \text{`{R}'}, \text{`{D}'}\}\); \(1 \le a_{i,1} < h\); \(1 \le |b_{i,1}| \le \frac{w}{2}\)). В третьей строке в том же формате описывается светофор с противоположной стороны перехода.

Наконец, в последней строке набора входных данных даны четыре целых числа \(i_1\), \(j_1\), \(i_2\) и \(j_2\) — координаты стартовой и конечной клеток, соответственно (\(1 \le i_1, i_2 \le n\); \(1 \le j_1, j_2 \le m\)).

Гарантируется, что все \((r_i, c_i)\) различны, а описания светофоров корректны: направления \(d_{i,1}\) и \(d_{i,2}\), указанные во вводе, противоположны и соответствуют направлениям, в которых от этого перехода расположен тротуар. Также гарантируется, что конечная клетка достижима из стартовой.

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

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

• Чтобы повернуть робота, выведите <<turn \(c\)>>, где \(c \in \{\text{`{L}'}, \text{`{U}'}, \text{`{R}'}, \text{`{D}'}\}\). В результате выполнения этого действия робот повернется <<лицом>> в соответствующем направлении, и интерактор выведет <<OK>> на отдельной строке.

• Чтобы переместить робота, выведите <<move>>. В таком случае робот переместится на одну клетку вперед в том направлении, в котором он повернут. Если это действие успешно, интерактор выведет <<OK>> на отдельной строке. Если при этом робот достиг конечной клетки \((i_2, j_2)\), интерактор перейдет к рассмотрению следующего набора входных данных и подаст соответствующие входные данные на ввод вашей программе (либо завершится и засчитает ваше решение, если это был последний набор входных данных).

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

• Чтобы сделать снимок, выведите <<camera>>. В ответ интерактор выведет \(h\) строк по \(w\) символов каждая. Каждый символ равен ‘r’, ‘g’ или ‘b’ и задает цвет соответствующего <<пикселя>>. Если непосредственно перед роботом не находится пешеходный переход, все символы будут случайными. Если же робот стоит у перехода, то два символа, соответствующие положению на <<изображении>> светофора напротив, будут отражать цвет этого светофора как описано в условии.

• Чтобы подождать \(t\) секунд (\(1 \le t \le 2 \cdot 10^6\)), выведите <<wait \(t\)>>. В ответ интерактор выведет <<OK>> на отдельной строке и обновит состояние всех светофоров, цвет которых за это время поменяется.

  Запрещается делать более \(25\) команд ожидания в одной и той же клетке поля. Если ваше решение совершает хотя бы \(26\) запросов ожидания из одной и той же клетки, интерактор в ответ выведет <<FAIL>> и завершится с вердиктом Wrong Answer.

Вывод каждой команды ваша программа должна завершать выводом символа перевода строки (endl, ‘\n’) и сбросом буфера вывода. Сбросить буфер можно с помощью

• <<fflush(stdout)>> в C и C++, или <<cout.flush()>> только в C++,

• <<System.out.flush()>> в Java,

• <<sys.stdout.flush()>> в Python,

• и <<Console.Out.Flush()>> в C#.

• В Pascal и Delphi сброс буфера при выводе в стандартный поток вывода происходит автоматически.

Решение, не выполняющее эти действия, может получить произвольный вердикт (скорее всего, Time Limit Exceeded или Idleness Limit Exceeded).

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

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

Во втором наборе входных данных в примере:

1. В клетке \((3, 2)\) нет перехода, поэтому по ней нельзя перемещаться;

2. При пересечении перехода в \((1, 2)\) в направлении ‘R’ светофор находится на высоте \(2\) и на расстоянии \(-2\) от центра: соответственно, его клетки на изображении располагаются в первом столбце во второй и третьей снизу строках. Для данного снимка они равны ‘b’ в верхней строке и ‘g’ во второй, поэтому его сразу можно пересекать.

3. При пересечении перехода в \((2, 3)\) в направлении ‘D’ светофор находится на высоте \(1\) и на расстоянии \(2\) от центра, то есть в четвертом столбце в двух нижних строках. На первом изображении он горит красным, а после ожидания (<<wait 10>>) — зеленым.

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

Глубина ямы равна H. Каждый школьник знает свой рост по плечи h_i и длину своих рук l_i. Таким образом, если он, стоя на дне ямы, поднимет руки, то его ладони окажутся на высоте h_i + l_i от уровня дна ямы. Школьники могут, вставая друг другу на плечи, образовывать вертикальную колонну. При этом любой школьник может встать на плечи любого другого школьника. Если под школьником i стоят школьники j₁, j₂, …, j_k, то он может дотянуться до уровня h_j1 + h_j2 + … + h_jk + h_i + l_i.

Если школьник может дотянуться до края ямы (то есть h_j1 + h_j2 + … + h_jk + h_i + l_i ≥ H), то он может выбраться из нее. Выбравшиеся из ямы школьники не могут помочь оставшимся.

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

Формат входных данных
В первой строке входных данных задается натуральное число N (1 ≤ N ≤ 2000) — количество школьников, попавших в яму.

Далее в N строках содержится по два целых числа: рост i-го школьника по плечи h_i (1 ≤ h_i ≤ 10⁵) и длина его рук l_i (1 ≤ l_i ≤ 10⁵).

В последней строке указано целое число — глубина ямы H (1 ≤ H ≤ 10⁵).

Формат выходных данных
В первой строке выведите K — максимальное количество школьников, которые смогут выбраться из ямы. Если K > 0, то во второй строке в произвольном порядке выведите их номера, разделяя их пробелами. Школьники нумеруются с единицы в том порядке, в котором они заданы во входных данных. Если существует несколько решений, выведите любое.