Информатика

Есть шарики, пронумерованные от \(1\) до \(n\). Также поступают \(q\) запросов:

• \(add\) \(x\) - добавить в дек шарик с номером \(x\). Вы можете положить шарик либо сверху, либо снизу дека.

• \(del\) \(x\) - удалить из дека шарик с номером \(x\). Вы находите шарик с номером \(x\) в деке, достаете все шарики НИЖЕ \(x\), удаляете шарик \(x\), потом кладете достанные шарики (без \(x\)) обратно в том же порядке.

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

Посчитайте, какое минимальное количество действий вы можете потратить.

Формат входных данных
Первая строка содержит числа \(n\) и \(q\) (\(1 \leq n, q \leq 2 \cdot 10^5\)) - максимальный номер шарика и количество запросов. Далее следуют \(q\) строк в формате:

• \(add\) \(x\) - добавить шарик с номером \(x\) (\(1 \leq x \leq n\)) в начало или конец дека.

• \(del\) \(x\) - удалить шарик с номером \(x\) (\(1 \leq x \leq n\)) из дека.

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

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

Замечание

В тесте 1 независимо от того, как вы добавите шарики, вы потратите 4 действия (на удаление и на добавление каждого из шариков).

В тесте 2 вам необходимо добавить шарик 5 вниз, шарик 8 вверх, шарик 1 вниз, шарик 4 вверх, тогда вы потратите ровно 6 действий.

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

На каждом уровне игры генерируется новый проспект из небоскребов, где каждая высотка задается уникальной положительной координатой относительно начала проспекта. После этого Похпид выбирает здание, с которого он начинает свой путь, при этом он может прыгать только на здание, координата которого больше текущей. Трудность этой игры заключается в том, что после каждого прыжка Похпид устает и уже не может прыгать также далеко как раньше. Формально говоря, на каждом уровне генерируется \(n\) зданий, координаты которых равны \(a_1, a_2, \ldots, a_n\). Игрок выбирает стартовый небоскреб и с него может прыгнуть на любое здание, которое находится правее, при этом длина первого прыжка может быть любой. Для всех последующих прыжков должно быть выполнено условие: если сейчас игрок находится на здании с координатой \(a_i\), а до этого был на позиции \(a_j\), то он может перепрыгнуть на здание с координатой \(a_k\), если \(a_i - a_j > a_k - a_i\).

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

Формат входных данных
В первой строке входных данных дается число уровней \(t\) \((1 \leq t \leq 1000)\).

В следующих строках каждый уровень задается числом зданий \(n\) \((1 \leq n \leq 5\,000)\) в одной строке и позициями этих зданий \(a_1, a_2, \ldots, a_n\) \((0 \leq a_i \leq 10 ^ {18}, \, a_i \neq a_j\) если \(i \neq j)\) в следующей строке. Гарантируется, что сумма \(n\) по всем уровням не превосходит \(30\,000\).

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

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

Решения, работающие при \(n \leq 100\) и \(t \leq 10\) будут получать не меньше 50% баллов.

Решения, работающие при \(n \leq 2500\) и \(t \leq 10\) будут получать не меньше 75% баллов.

В первом примере оптимальный выбор небоскребов \(3, 5, 4, 1\) их координаты соответственно будут равны \(3, 6, 8, 9\).

Во втором примере ответы для уровней получаются выбором следующих 3 наборов индексов соответственно:
1) \(2, 1, 3\)
2) \(3, 2, 8, 7, 5\)
3) \(5, 1, 4, 2\)

Миша сидел на занятиях математики в Высшей школе экономики и решал следующую задачу: дано \(n\) целых чисел и нужно расставить между ними знаки \(+\) и \(\times\) так, чтобы результат полученного арифметического выражения был нечётным (например, между числами \(5\), \(7\), \(2\), можно расставить арифметические знаки следующим образом: \(5 \times 7 + 2 = 37\)). Так как примеры становились все больше и больше, а Миша срочно убегает в гости, от вас требуется написать программу решающую данную задачу.

Формат входных данных
В первой строке содержится единственное число \(n\) (\(2 \leq n \leq 10^5\)). Во второй строке содержится \(n\) целых чисел \(a_i\), разделённых пробелами (\(-10^9 \leq a_i \leq 10^9\)). Гарантируется, что решение существует.

Формат выходных данных
В одной строке выведите \(n - 1\) символ \(+\) или \(\times\), в результате применения которых получается нечётный результат. (Для вывода используйте соответственно знаки <<+>> (ASCII код—43) и <<x>> (ASCII код—120), без кавычек).

 

У радиолюбителя Алексея есть девятисегментный жидкокристаллический индикатор, который может показывать цифры от \(0\) до \(9\) в виде цифр <<почтового индекса>> (см. рисунок):

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

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

Формат входных данных
Первая строка входных данных содержит число \(n\) (\(1 \le n \le 10\)) — количество цифр, которые смог показать на индикаторе Алексей.

Следующие \(n\) строк содержат по одной цифре \(a_i\) (\(0 \le a_i \le 9\)) — сами цифры, которые Алексей смог показать. Гарантируется, что все \(a_i\) различны.

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

 

Маша, Даша, Миша и Саша играют с числами. Каждый из них написал некоторое множество целых чисел. Затем они выполнили следующие операции. 
1) Ребята нашли разницу между Машиным и Дашиным множествами.
2) Затем, они объединили множества чисел Миши и Саши.
3) В конце, они нашли общие элементы двух множеств, полученных в результате первой и второй операции. 

Выведите на экран в порядке возрастания числа, которые получились у Маши, Даши, Миши и Саши в результате выполнения третьей операции.

Формат входных данных
Программа получает на вход четыре пары строк (всего восемь строк), в каждой паре строк первая строка содержит целое число Ni - количество чисел в i-й строке (1 <= N <= 106, 1 <= i <= 4), вторая строка каждой пары строк содержит множество целых чисел, разделенных одним пробелом. Во второй строке записано множество чисел Маши, во четвертой - Даши, в шестой - Миши, в восьмой - Саши. Каждое число по модулю не превышает 10⁵.

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

Всего во Флатландии \(n\) городов, пронумерованных от \(1\) до \(n\), столица Флатландии имеет номер \(1\). Компьютерная сеть Флатландии устроена следующим образом: в каждом городе есть один центр подключения, который может быть связан с некоторыми другими центрами с помощью проводных каналов связи. При этом между любыми двумя городами есть ровно один маршрут по каналам связи, иначе говоря, сеть представляет собой дерево. Для города \(i\), где \(i > 1\), обозначим первый город на маршруте от города \(i\) до столицы как \(p_i\).

Запланирована модернизация сети Флатландии, в результате которой некоторые каналы связи будут заменены на более современные оптические. Оптические каналы могут быть проложены только вместо существующих проводных. Стоимость замены канала, который соединяет город \(i\) с городом \(p_i\), равна \(w_i\). Из-за ограничений технологии любой центр подключения может быть подключен оптическими каналами не более чем к \(k\) другим центрам.

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

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

Формат входных данных
На первой строке ввода находятся два целых числа \(n\) и \(k\) (\(2 \le n \le 10^5\), \(1 \le k \le 100\)).

На следующих \(n - 1\) строках заданы описания каналов, \((i-1)\)-я из этих строк содержит два целых числа: \(p_i\) и \(w_i\) (\(1 \le p_i \le i\), \(0 \le w_i \le 10^9\)).

Формат выходных данных
Выведите два целых числа \(cnt\) и \(cost\): максимальное число каналов, которое удастся модернизировать и минимальную стоимость, за которую можно модернизировать такое число каналов.

Замечание
Конфигурация сети в первом примере до и после модернизации показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно \(4\). Стоимость модернизации любого канала равна \(0\) и не показана.

Есть и другие подходящие решения, в которых модернизируется \(4\) канала.

Конфигурация сети во втором примере до и после модернизациии показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно \(6\). Стоимость модернизации канала показана рядом с каналом, суммарная стоимость модернизации каналов в оптимальном решении равна \(27\).

Тимофей готовится к ЕГЭ. Для отработки навыка скорости и точности поиска ответов на задания по теме «Системы счисления» ему часто приходится решать примеры типа «сколько значащих нулей (или единиц) содержит двоичная запись значения выражения 2^a + 2^b − 2^c?». Значащими называются все цифры, кроме нулей в начале числа (которые обычно и не записываются). Например, десятичное число 20 в двоичной системе счисления записывается как 10100, и в этой записи две значащие цифры «1» и три значащие цифры «0».

Помогите Тимофею по известным a, b и c узнать ответ на задачу.

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

Программа получает на вход четыре целых неотрицательных числа: a, b, c и d, записанные в отдельных строках. Числа a, b и c соответствуют показателям степеней двоек в задании (0 ≤a, b, c, ≤10⁹). При этом гарантируется, что 2^a + 2^b − 2^c > 0 и a ≠ b.

Число d равно либо 0, либо 1 — цифра, количество которых в значении выражения нужно узнать.

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

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

Пример

Ввод	Вывод	Пояснение
4 3 2 1	2	Нужно узнать количество единиц в двоичной записи значения выражения 24 + 23 − 22. Вычислим: 16 + 8 - 4 = 20. 2010 = 101002. Всего две единицы. Такой же результат можно получить, выполнив действия в столбик, не переводя числа в десятичную систему счисления (см. ниже).

 10000
+ 1000
 -----
 11000

 11000
-  100
 -----
 10100

Кате нравятся целые числа, которые делятся без остатка на число K, а Маше — целые числа, которые делятся без остатка на число M. Сегодня подруги решили утроить соревнование и выяснить, чьи любимые числа лучше.

Для начала они выписали на лист бумаги все целые числа от A до B включительно. Затем Катя посчитала, сколько чисел среди выписанных делятся на число K без остатка, а Маша посчитала, сколько чисел делятся на число M без остатка.

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

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

Программа получает на вход четыре целых положительных числа, записанных в отдельных строках: K, M, A и B. Числа не превосходят 2×10⁹.

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

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

Примеры

Ввод	Вывод	Пояснение
2 3 2 9	1	Выписаны числа 2, 3, 4, 5, 6, 7, 8, 9. Среди них есть четыре числа, которые делятся на 2: 2, 4, 6, 8, и три числа, которые делятся на 3: 3, 6, 9. Ответ: 4 - 3 = 1.
3 3 6 6	0	Выписано одно число 6 и оно является любимым числом как Кати, так и Маши.
10 2 1 5	-2	Среди чисел 1, 2, 3, 4, 5 нет ни одного любимого числа Кати, а у Маши любимыми являются 2 и 4.

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

Каждая елочка имеет свою красоту, равную количеству ветвей с одной стороны ствола и (так уж совпало) длине самой нижней ветви. Каждая следующая верхняя ветка на одну клетку короче предыдущей. Между ветвями, а также под самой нижней и над самой верхней ветвями, находится ствол дерева шириной ровно в одну клетку. На рисунке вы видите елки кисти Тимофея красотой от 0 до 5 включительно.

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

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

Программа получает на вход одно целое число n — красоту ёлки (0 ≤ n ≤ 2×10⁹).

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

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

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

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

2100 год. Схема сборки избы осталась прежней, а вот дерево заменено более стойким к внешним воздействиям полимерным материалом. Строители из длинной заготовки длины c отрезают бревна нужной длины и укладывают их друг на друга. На фундамент кладут два длинных бревна длины b, на них — три коротких длины a, снова два длинных, опять три коротких, и так далее. Самый верхний ряд всегда делают из трех коротких бревен.

По данным значениям a, b и c определите максимальную высоту избы, которую можно построить из одной заготовки. Каждые пять уложенных брёвен (два длинных и три коротких) увеличивают высоту дома на 1.

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

Программа получает на вход три целых числа a, b и c — длины брёвен и заготовки (1 ≤ a < b < c ≤ 10¹⁸), записанных в отдельных строках.

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

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

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

Замечание
Cтроители уложат в первый ряд два продольных бревна, отрезав от заготовки длиной 29 ровно 10 единиц длины. Потом уложат три поперечных бревна, отрезав от заготовки еще 9 единиц длины. Уложено 5 бревен, высота избы 1. От заготовки осталось 10 единиц длины, их как раз хватит на ряд из длинных бревен, но на следующий ряд заготовки уже не хватит.

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

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

Формат входных данных
Программа получает на вход три целых положительных числа, не превосходящих \(10^5\) каждое, по одному в строке, в том порядке, в котором они шли на доске.

Формат выходных данных
В первой строке выведите число, которое Вове необходимо написать. Можно доказать, что это число обязательно должно быть целым. В записи этого числа не должно быть десятичной точки, то есть вывод <<\(13{.}0\)>> вместо <<13>> является неправильным.

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

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

В примере из условия Вова увидел на доске числа \(10\), \(16\) и \(19\). Если он напишет на доску между первым и вторым из них число \(13\), то в получившейся четверке чисел \(10~13~ 16~19\) разность между четвертым и третьим (\(19 - 16\)), третьим и вторым (\(16 - 13\)) и вторым и первым (\(13 - 10\)) окажется одна и та же, поэтому эта четверка будет арифметической прогрессией.

Для получения одной награды нужно предъявить \(10\) жёлтых билетиков. \(10\) красных билетиков можно заменить на один жёлтый. \(10\) синих билетиков можно заменить на один красный. У Тома сейчас \(y\) жёлтых билетиков, \(r\) красных и \(b\) синих. Сколько наград Том может получить?

Формат входных данных
Три строки входных данных содержат три натуральных числа: \(y\), \(r\) и \(b\). Все числа не превосходят \(2 \times 10^9\).

Формат выходных данных
Выведите одно неотрицательное целое число — количество наград, которые может получить Том. В записи этого числа не должно быть десятичной точки, то есть вывод <<\(1{.}0\)>> вместо <<1>> является неправильным.

Замечание

Пример из условия соответствует эпиграфу. Том обменяет \(10\) синих билетиков на \(1\) красный, после чего у него станет \(9+1=10\) красных билетиков. Далее он обменяет эти \(10\) красных билетиков на \(1\) жёлтый, и у него станет \(9+1=10\) жёлтых билетиков. В конце он обменяет эти \(10\) жёлтых билетиков на одну награду.

Головоломка состоит из \(n\) треугольников. Чтобы решить головоломку, необходимо выбрать из них четыре треугольника и собрать из них большой треугольник по следующей схеме:

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

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

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

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

В второй строке дано одно целое число \(n\) — количество треугольников в головоломке (\(4 \le n \le 30\)).

В следующих \(n\) строках дано описание треугольников. Один треугольник описывается координатами трех своих углов, данных в порядке обхода треугольника против часовой стрелки. Все координаты целые и по модулю не превышают \(10^5\). Гарантируется, что треугольники не являются вырожденными. В исходном расположении треугольники могут пересекаться.

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

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

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

Во втором примере все треугольники имеют одинаковую форму прямоугольного треугольника с длинами катетов равными \(1\). Из любых четырех треугольников можно собрать один.

Компания <<Flatland Dynamics>> разрабатывает прыгающего робота. Для испытания робота используется полигон, на котором организован круговой маршрут из \(n\) специальных платформ, пронумерованных от \(1\) до \(n\). Расстояние между \(i\)-й и \(i+1\)-й платформой равно \(d_i\), аналогично расстояние между \(n\)-й и \(1\)-й платформой равно \(d_n\).

Робот оснащен искусственным интеллектом и в процессе испытания учится прыгать все дальше. В любой момент времени робот характеризуется своей ловкостью — целым числом \(a\). Робот может перепрыгнуть с платформы \(i\) на платформу \(i+1\), если \(a \ge d_i\). Аналогично, прыжок с \(n\)-й платформы на \(1\)-ю возможен, если \(a \ge d_n\). При этом после каждого прыжка ловкость робота увеличивается на \(1\).

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

Формат входных данных
На первой строке ввода находится число \(n\) (\(3 \le n \le 10^7\)).

Вторая строка содержит одно целое число \(f\), которое описывает формат, в котором задан массив расстояний между платформами.

Если \(f = 1\), то на третьей строке находятся \(n\) целых чисел \(d_1, d_2, \ldots, d_n\) (\(1 \le d_i \le 10^{9}\)).

Если \(f = 2\), то на третьей строке находится число \(m\) \(\left(2 \le m \le \min(n, 10^5)\right)\) и три целых числа \(x\), \(y\) и \(z\) (\(0 \le x, y, z \le 10^9\)). На четвертой строке находятся \(m\) целых чисел \(c_1, c_2, \ldots, c_m\) (\(1 \le c_i \le 10^9\)). Значения \(d_i\) вычисляются по следующим формулам.

Если \(1 \le i \le m\), то \(d_i = c_i\).

Если \(m + 1 \le i \le n\), то \(d_i = \left((x\cdot d_{i-2} + y\cdot d_{i-1} + z)\bmod 10^9\right) + 1\).

Здесь \(\bmod\) означает остаток от целочисленного деления, в языках C++, Java и Python он обозначается символом <<%>>.

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

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

Замечание
Во втором примере массив расстояний между платформами равен \([1, 2, 3, 4, 5, 18, 45, 112, 273, 662]\). Значения от \(d_6\) до \(d_{10}\) вычисляются по формулам:

\(d_6 = \left((1\cdot d_4+2\cdot d_5 + 3) \bmod 10^9\right)+1 = \left((1\cdot 4+2\cdot 5+3)\bmod 10^9\right)+1=18\)

\(d_7 = \left((1\cdot d_5+2\cdot d_6 + 3) \bmod 10^9\right)+1 = \left((1\cdot 5+2\cdot 18+3)\bmod 10^9\right)+1=45\)

\(d_8 = \left((1\cdot d_6+2\cdot d_7 + 3) \bmod 10^9\right)+1 = \left((1\cdot 18+2\cdot 45+3)\bmod 10^9\right)+1=112\)

\(d_9 = \left((1\cdot d_7+2\cdot d_8 + 3) \bmod 10^9\right)+1 = \left((1\cdot 45+2\cdot 112+3)\bmod 10^9\right)+1=273\)

\(d_{10} = \left((1\cdot d_8+2\cdot d_9 + 3) \bmod 10^9\right)+1 = \left((1\cdot 112+2\cdot 273+3)\bmod 10^9\right)+1=662\)

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


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


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

Определите, сколько раз выполнится тело цикла, а также последнее число, которое будет выведено на экран в процессе выполнения программы. В ответе запишите два числа через пробел: сначала сколько раз выполнится цикл, затем последнее выведенное число. Если программа ничего не выводит на экран, то в вместо второго числа напишите слово None.

var n: integer;
begin
  n := {1};
  while n >= {2} do
  begin
    writeln(n);
    n := n - {3};
  end;
end.

Определите, сколько раз выполнится тело цикла, а также последнее число, которое будет выведено на экран в процессе выполнения программы. В ответе запишите два числа через пробел: сначала сколько раз выполнится цикл, затем последнее выведенное число. Если программа ничего не выводит на экран, то в вместо второго числа напишите слово None.

n = {1}
while n >= {2}:
    print(n)
    n = n - {3}

Определите, сколько раз выполнится тело цикла, а также последнее число, которое будет выведено на экран в процессе выполнения программы. В ответе запишите два числа через пробел: сначала сколько раз выполнится цикл, затем последнее выведенное число. Если программа ничего не выводит на экран, то в вместо второго числа напишите слово None.

var n: integer;
begin
  n := {1};
  while n < {2} do
  begin
    writeln(n);
    n := n + {3};
  end;
end.

Определите, сколько раз выполнится тело цикла, а также последнее число, которое будет выведено на экран в процессе выполнения программы. В ответе запишите два числа через пробел: сначала сколько раз выполнится цикл, затем последнее выведенное число. Если программа ничего не выводит на экран, то в вместо второго числа напишите слово None.

n = {1}
while n < {2}:
    print(n)
    n = n + {3}

Даны два целых числа \(x\) и \(y\). Назовем последовательность \(a\) длины \(n\) модообразной, если \(a_1=x\), и для всех \(1 < i \le n\) значение \(a_{i}\) равно либо \(a_{i-1} + y\), либо \(a_{i-1} \bmod y\). Здесь \(x \bmod y\) обозначает остаток от деления \(x\) на \(y\).

Определите, существует ли модообразная последовательность длины \(n\), сумма элементов которой равна \(S\), и если существует, то найдите любую такую последовательность.

Формат входных данных
Первая и единственная строка содержит четыре целых числа \(n\), \(x\), \(y\) и \(S\) (\(1 \le n \le 200\,000\), \(0 \le x \le 200\,000\), \(1 \le y \le 200\,000\), \(0 \le S \le 200\,000\)) — длина последовательности, параметры \(x\) и \(y\), и необходимая сумма элементов последовательности.

Формат выходных данных
Если искомая последовательность существует, выведите в первой строке <<Yes>> (без кавычек). Далее, во второй строке выведите \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) через пробел — элементы последовательности \(a\). Если подходящих последовательностей несколько, выведите любую из них.

Если же последовательность не существует, выведите в единственной строке <<No>>.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки <<yEs>>, <<yes>>, <<Yes>> и <<YES>> будут приняты как положительный ответ.

Замечание
В первом примере условиям удовлетворяет последовательность \([8, 11, 2, 5, 2]\). Таким образом, \(a_1 = 8 = x\), \(a_2 = 11 = a_1 + 3\), \(a_3 = 2 = a_2 \bmod 3\), \(a_4 = 5 = a_3 + 3\), \(a_5 = 2 = a_4 \bmod 3\).

Во втором примере первый элемент последовательности должен равняться \(5\), поэтому последовательность \([2, 2, 2]\) не подходит.