Информатика

У радиолюбителя Алексея есть девятисегментный жидкокристаллический индикатор, который может показывать цифры от \(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]\) не подходит.

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

Армия жителей Средиземья будет состоять из нескольких отрядов. Известно, что каждая пара существ одной расы, которые находятся в разных отрядах, прибавляет \(b\) единиц к суммарной силе армии. Но так как Тимофею будет сложно руководить армией, состоящей из большого числа отрядов, то суммарная сила армии, состоящей из \(k\) отрядов, уменьшается на \((k - 1) \cdot X\) единиц. Обратите внимание, что армия всегда состоит из хотя бы одного отряда.

Известно, что в Средиземье проживают \(n\) рас, и количество существ \(i\)-й расы равно \(c_i\). Помогите жителям Средиземья определить максимальную силу армии, которую они могут составить.

Формат входных данных
Первая строка входных данных содержит три целых числа \(n\), \(b\) и \(X\) (\(1 \le n \le 200\,000\), \(1 \le b \le 10^6\), \(0 \le X \le 10^9\)) — количество рас и константы \(b\) и \(X\), описанные выше.

Вторая строка содержит \(n\) целых чисел \(c_1, c_2, \ldots, c_n\) (\(1 \le c_i \le 200\,000\)) — количество существ каждой из \(n\) рас.

Гарантируется, что \(c_1 + c_2 + \ldots + c_n \le 200\,000\).

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

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

Замечание

В первом примере жители Средиземья могут составить \(3\) отряда. Так как \(X = 0\), то сила армии не уменьшится из-за количества отрядов. Далее жителей по отрядам можно распределить так:

• Единственного представителя первой расы можно отправить в первый отряд.

• Первого представителя второй расы можно отправить в первый отряд, второго представителя второй расы можно отправить во второй отряд. Тогда суммарная сила армии увеличится на \(b = 1\).

• Первого представителя третьей расы можно отправить в первый отряд, второго представителя третьей расы можно отправить во второй отряд, третьего представителя третьей расы можно отправить в третий отряд. Тогда суммарная сила армии увеличится на \(3 \cdot b = 3\), так как они образуют три пары, находящиеся в разных отрядах.

Таким образом, суммарная сила армии равна \(4\).

В известной школе прошёл урок физкультуры. Как полагается, всех построили в шеренгу и попросили рассчитаться на <<первый–\(k\)-й>>.

Как известно, расчёт на <<первый–\(k\)-й>> происходит следующим образом: первые \(k\) человек имеют номера \(1, 2, 3, \ldots, k\), следующие \(k - 1\) человек имеют номера \(k - 1, k - 2, \ldots, 1\), следующие \(k - 1\) человек имеют номера \(2, 3, \ldots, k\) и т.д. Таким образом, расчёт повторяется через каждые \(2k - 2\) позиции. Примеры расчёта приведены в разделе <<Замечание>>.

Мальчик Вася постоянно всё забывает. Например, он забыл позицию, которую занимал в шеренге. Но он помнит число \(k\), описанное выше, номер, который он получил при расчёте, а также, что его позиция в шеренге была не больше \(n\). Другими словами, если Вася стоял на позиции \(y\) в шеренге, то \(y \leq n\). Помогите Васе понять, сколько есть различных позиций в ряду, где он мог стоять.

Формат входных данных
Первая строка содержит одно целое число \(k\) (\(2 \leq k \leq 10^9\)) — характеристика расчёта, описанная в условии.

Вторая строка содержит одно целое число \(x\) (\(1 \leq x \leq k\)) — номер, который Вася получил при расчёте.

Третья строка содержит одно целое число \(n\) (\(x \leq n \leq 10^9\)) — верхнее ограничение на позицию Васи.

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

Замечание

В первом примере подходят позиции равные \(2, 4, 6, 8, 10\).

Во втором примере подходят позиции равные \(2, 4, 6, 8, 10\).

В третьем примере подходят позиции равные \(3\) и \(7\).

Пример расчёта для \(k = 2\), \(k = 3\) и \(k = 5\):

У Пети есть прямоугольник размера \(a \times b\) с целыми сторонами, хотя бы одна из которых больше \(1\). Он пробует разрезать этот прямоугольник на два прямоугольника с целыми сторонами, сделав разрез, параллельный какой-то из сторон исходного прямоугольника. Затем Петя пытается из двух получившихся прямоугольников сложить какой-то отличный от исходного прямоугольник, при этом он может как угодно поворачивать и двигать эти два прямоугольника. Если у него получается это сделать, то он называет прямоугольник \(a \times b\) интересным.

Обратите внимание, что если два прямоугольника отличаются поворотом на \(90^{\circ}\), то они считаются одинаковыми. Например, прямоугольники \(6 \times 4\) и \(4 \times 6\) считаются одинаковыми.

Таким образом, прямоугольник \(2 \times 6\) является интересным, потому что его можно разрезать на два прямоугольника \(2 \times 3\), после чего из этих двух прямоугольников сложить прямоугольник \(4 \times 3\), который отличается от прямоугольника \(2 \times 6\).

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

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

Формат входных данных
Первая и единственная строка содержит одно целое число \(n\) (\(2 \le n \le 2 \cdot 10^9\)) — ограничение на длину сторон прямоугольника.

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

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

Замечание

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

Во втором примере прямоугольники \(2 \times 2\) и \(2 \times 3\) являются интересными. Прямоугольник \(2 \times 3\) можно разрезать на два прямоугольника \(1 \times 3\), а из них можно сложить прямоугольник \(1 \times 6\). Прямоугольник \(3 \times 3\) не является интересным, потому что его можно разрезать только на два прямоугольника \(1 \times 3\) и \(2 \times 3\), но из них можно сложить только прямоугольник \(3 \times 3\). Обратите внимание, что прямоугольники \(2 \times 3\) и \(3 \times 2\) считаются одинаковыми, поэтому в ответе их нужно учесть только один раз.