Информатика

Магазины в рекламных целях часто устраивают распродажи. Так, например,одна из крупных сетей магазинов канцелярских товаров объявила два рекламных предложения: "купи N одинаковых товаров и получи еще один товар бесплатно"и "купи K товаров по цене K−1 товара".

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

Входные данные
Во входном файле записаны целые числа N, K, A и B (1 ≤ N ≤ 100, 2 ≤ K ≤ 100, 1 ≤ A ≤ 10⁹, 1 ≤ B ≤ 10⁹), разделенные пробелами.

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	4 4 13 2	8
2	3 4 8 3	2
3	3 4 7 1	9

Ушан решил сыграть в карточную игру. У него есть колода, состоящая из N съедобных карт. На i-й карте сверху написано целое число Ai. Ушан выполняет описанную ниже операцию ноль или более раз, так что значения, записанные на оставшихся карточках, будут попарно различны.
Найдите максимально возможное количество оставшихся карт. Здесь N нечетное, что гарантирует сохранение хотя бы одной карты. 
Операция: вынуть из колоды три произвольные карты. Из этих трех карт съешьте две: одну с наибольшим значением, а другую с наименьшим значением. Затем верните оставшуюся одну карту в колоду.

Входные данные
В первой строке записано нечетное число N (\(3<=N<=10^5\)). Во второй строке записаны N чисел Ai (\(1<=A_i<=10^5\))

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

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	5 1 2 1 3 7	3	Оптимальное решение - выполнить операцию один раз, вынув две карты с 1 и одну карту с 2. Одна карта с 1 и другая с 2 будут съедены, а оставшаяся карта с 1 будет возвращена в колоду. Тогда значения, написанные на оставшихся картах в колоде, будут попарно различными: 1, 3 и 7.
2	15 1 3 5 2 1 3 2 8 8 6 2 6 11 1 1	7

 

Вам даны два целых числа K и S. Три переменные X, Y и Z принимают целые значения, удовлетворяющие условию \(0<=X,Y,Z<=K\). Сколько существует различных значений X, Y и Z, таких что \(X+Y+Z=S\)?

Входные данные
На вход подается два целых числа K (\(2<=K<=2500\)) и S (\(0<=S<=3\cdot K\)).

Выходные данные
Выведите количество троек X, Y и Z, удовлетворяющих условию.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	2 2	6	Есть шесть троек X, Y и Z, которые удовлетворяют условию: Х = 0, Y = 0, Z = 2 Х = 0, Y = 2, Z = 0 Х = 2, Y = 0, Z = 0 Х = 0, Y = 1, Z = 1 Х = 1, Y = 0, Z = 1 Х = 1, Y = 1, Z = 0
2	5 15	1	Лишь одна тройка удовлетворяют условию задачи: Х = 5, Y = 5, Z = 5

 

Дана последовательность из N целых чисел (они могут быть положительными, отрицательными или равными 0). Необходимо выбрать из этих чисел два числа так, чтобы их произведение было как можно меньшим (не рассматриваются квадраты данных чисел, но можно выбрать произведение двух различных элементов последовательности, равных друг другу).
В первой строке входных данных записано целое число N, 2 ≤ N ≤10⁵ – количество данных чисел. Следующие N строк содержат сами числа, не превосходящие по модулю 40 000.
Программа должна вывести единственное целое число – наименьшее возможное произведение двух различных элементов этой последовательности.

Примеры

№	Входные данные	Выходные данные
1	3 1 -3 2	-6

Для пополнения бюджета в стране Авалон, известной своими горными туристическими маршрутами, ввели новый налог для туристов. Величина налога
пропорциональна длине маршрута, но, поскольку маршрут проходит по горам и пройденное расстояние, зависящее от высоты спуска и подъёма, подсчитать сложно, налог считается без
учёта высоты, то есть величина налога пропорциональна горизонтальному перемещению, совершённому туристической группой. Кроме того, в силу старинного обычая все
туристические группы должны перемещаться по горам Авалона строго с запада на восток. Турфирма хочет сэкономить на налоге, поэтому она хочет разработать туристический
маршрут с минимальной величиной налога. При этом, поскольку маршрут является горным, он должен содержать подъём в гору и спуск с горы, то есть на маршруте должна быть точка,
которая находится строго выше начала и конца маршрута. 
Турфирма составила карту гор Авалона, содержащую информацию о высоте гор при передвижении с запада на восток. Высоты гор измерены в точках через равные расстояния. 
Найдите на данной карте гор Авалона туристический маршрут минимальной длины, удовлетворяющий условию наличия подъёма и спуска.
Первая строка входных данных содержит число N – количество точек на карте гор Авалона. Следующие N строк содержат информацию о высоте гор в данных N точках при движении с запада на восток. Все числа натуральные, не превосходящие 10⁵.
Программа должна вывести два числа – номер точки начала маршрута и номер точки окончания маршрута. Точки нумеруются от 1 до N. Если маршрута, удовлетворяющего
условиям, не существует, программа должна вывести одно число 0.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 18 10 15 20 20 10 3	3 6	Дано 7 точек с высотами 18, 10, 15, 20, 20, 10, 3. Самый короткий маршрут, содержащий подъём и спуск, – это 15, 20, 20, 10. Он начинается в точке номер 3 и заканчивается в точке номер 6.
2	3 9 8 5	0	Высота гор монотонно убывает, поэтому искомого маршрута не существует.

Антонин, Бальбин и Цезарь играют в игру "Карты на троих", алгоритм которой следующий:
- сначала у каждого из трех игроков есть колода, состоящая из некоторого количества карт. На каждой карточке написана буква a, b или c. Порядок карт в колодах не может быть изменен;
- игроки ходят по очереди. Антонин ходит первым;
- если в колоде текущего игрока есть хотя бы одна карта, ему необходимо сбросить верхнюю карту в колоде;
- следующий ход переходит к игроку, имя которого начинается с буквы на сброшенной карте (a - Антонин, b - Бальбин, c - Цезарь);
- если колода текущего игрока пуста, игра заканчивается, и текущий игрок выигрывает игру.
Вам выдаются начальные колоды игроков (Sa, Sb, Sc). Состояние колоды Антонина записано в строке Sa, где i-й (\(1<=i<=len(S_a)\)) символ это буква в i-й карты в колоде. Строка Бальбина (Sb) и строка Цезаря (Sс) описываются таким же образом. 
Определите победителя в игре.

Формат входных данных
На вход подаются три ненулевых строки Sa, Sb и Sc, каждая с новой строки. Длина каждой строки не более 100 символов. Каждая строка состоит только из букв a, b или c.

Формат выходных данных
Если выиграл Антонин. то выведите букву A, если Бальбин - букву B, если Цезарь - букву C.

Примечание 
В первом тестовом примере игра будет развиваться следующим образом:
Антонин сбрасывает верхнюю карту своей колоды, a. Антонин делает следующий ход.
Антонин сбрасывает верхнюю карту своей колоды, с. Цезарь следующий.
Цезарь сбрасывает верхнюю карту своей колоды, с. Цезарь следующий.
Цезарь сбрасывает верхнюю карту своей колоды: a. Антонин делает следующий ход.
Антонин сбрасывает верхнюю карту своей колоды: a. Антонин делает следующий ход.
Колода Антонина пуста. Игра заканчивается, и Антонин выигрывает игру.

 

У Громозеки есть N целых чисел a1,a2,..,aN. Его цель -  получить N равных целых чисел, преобразовав некоторые из них. Он может преобразовать каждое целое число не более одного раза. Преобразование целого числа x в другое целое число y стоит ему \((x-y)^2 \) рублей. Даже если \(a_i = a_j\) (\(i \neq j\)) он должен отдельно оплатить стоимость преобразования каждого из них (см. пример 2). 
Найдите минимальную общую стоимость для достижения цели Громозеки.

Входные данные
В первой строке задается число N (\(1<=N<=100\)). Во второй строке числа a1,a2,..,aN (\(100<=a_i<=100\)).

Выходные данные
Выведите минимальную общую стоимость для достижения цели Громозеки.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	2 4 8	8	Минимальная по сумме трансформация обоих чисел - это преобразование каждого числа в 6 будет: (4-6)2+(8-6)2=8 рублей.
2	3 1 1 3	3	Трансформируем все числа в 2: (1-2)2+(1-2)2+(3-2)2=3  рубля. Громозека обязан заплатить \((1-2)^2\) рубля за каждое преобразованное число 1.
3	3 4 2 5	5	Трасформируем 2 и 5 в число 4: (2-4)2+(5-4)2=5 рублей.
4	4 -100 -100 -100 -100	0	Ничего не надо преобразовывать.

 

Физики проводят эксперимент для исследования частиц трёх типов: x, y и z. Они запускают в коллайдер пронумерованный ряд из n частиц. Во время эксперимента происходит воздействие на одну конкретную частицу, после чего частица исчезает с i-ого места ряда и моментально появляется на месте j. После её исчезновения номера частиц, стоящих правее, уменьшаются на 1, а после появления, номера частиц, стоящих правее, увеличиваются на 1. После определенного числа воздействий физики интересуются какая частица стоит на месте k. Напишите программу, которая поможет физикам.

Входные данные
В первой строке файла два целых числа: n – количество частиц и m — общее количество воздействий и вопросов (1 ≤ n ≤ 1000000, 1 ≤ m ≤ 15000). Во второй строке — последовательность из символов x, y и z длиной n. На каждой из следующих m строк (1 ≤ m ≤ 15000) описано воздействие или вопрос. Строка, в которой описано воздействие, начинается символом a и после пробела дается два целых числа из интервала [1; n]. Первое из них показывает начальное, а второе  - конечное местоположение частицы во время воздействия. Строка, в которой описан вопрос, начинается символом q и после пробела дается одно целое число из интервала [1; n]. Оно указывает позицию, которая интересует физиков.

Выходные данные
Выведите столько строк, сколько вопросов во входном файле. В строке номер i надо записать ответ на вопрос i — название соответствующей частицы x, y или z.

Пояснения к примеру
Последовательность после первого воздействия – xxyyzxxzxzyyzyx, последовательность после второго воздействия – xxyxyzxxzxzyyzy, последовательность после третьего воздействия – xyxyxyzxxzxzyzy,
 

Примеры

№	Входные данные	Выходные данные
1	15 6 xzxyyzxxzxyyzyx a 2 10 a 15 4 q 3 a 12 2 q 14 q 2	y z y

Дана возрастающая последовательность целых чисел 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, ... Она сформирована следующим образом: берется одно нечетное число, затем два четных, затем три нечетных и так далее. Выведите N-й элемент этой последовательности.

Входные данные
Одно целое число N (1 ≤ N ≤ 10¹⁰⁰).

Выходные данные
Выведите одно целое число - N-й элемент последовательности.

Примеры

№	Входные данные	Выходные данные
1	1	1
2	4	5

В многопользовательской игре Agar.io игроки управляют бактериями. У каждой бактерии есть размер — целое положительное число. Если встречаются две бактерии разного размера, то бактерия большего размера поглощает меньшую бактерию. При этом меньшая бактерия исчезает, а размер большей бактерии увеличивается на размер меньшей бактерии. Если встречаются две бактерии равного размера, то ничего не происходит. Побеждает игрок, чья бактерия останется на игровом
поле одна.
В игре участвуют n игроков, вам даны размеры их бактерий. Определите, какие из игроков имеют возможность выиграть в этой игре.

Формат входных данных
Программа получает на вход целое число n, 1 ≤ n ≤ 10⁵ — количество игроков. Следующие n строк содержат по одному числу a_i — размеры бактерий, 1 ≤ a_i ≤ 10⁹. Числа a_i заданы в порядке неубывания.
Формат выходных данных
Программа должна вывести n чисел равных «0» или «1», по одному числу в строке. Если i-е число равно 0, то это означает, что i-й игрок (размер бактерии которого первоначально был равен
a_i) ни при каких обстоятельствах не может выиграть в этой игре. Если i-е число равно 1, то это означает, что i-й игрок имеет возможность выиграть в этой игре.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 1 1 3 4	0 0 1 1	В примере из условия 4 бактерии размерами 1, 1, 3, 4. Бактерии размером 1 никого не могут съесть, поэтому не могут выиграть. Бактерия размером 4 может съесть всех. Бактерия размером 3 может съесть по очереди две бактерии размером 1. Тогда её размер станет 5, после этого она сможет съесть бактерию размером 4 и выиграть. Ответ: 0, 0, 1, 1.

Бесконечную таблицу, строки и столбцы которой пронумерованы целыми числами начиная с 1 сверху вниз и слева направо, заполняют целыми числами 1, 2, 3 и т.д. Числа выписываются в
соседние клетки по границам квадратов увеличивающегося размера (см. рисунок).


Формат входных данных
Программа получает на вход одно целое число n, 1 ≤ n ≤ 10¹⁸
Формат выходных данных
Программа должна вывести два целых числа: номер строки и номер столбца, в которых находится число n в этой таблице. Запись выводимых чисел должна содержать только цифры, вывод
действительных чисел в ответе считается неверным.

Примеры

№	Входные данные	Выходные данные
1	15	4 2

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

Придя в цветочный магазин, Володя обнаружил, что букет можно составлять из цветов m различных видов, причём количество цветов каждого вида не ограничено. Володя знает, что от первого цветка i-го вида в букете его супруга становится счастливее на a_i, а от каждого следующего цветка  
такого вида она становится счастливее на b_i. То есть, если в букете x_i > 0 цветов вида i, то от цветов этого вида жена Володи становится счастливее на a_i + (x_i − 1) · b_i.

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

Формат входных данных
В первой строке вводятся два целых числа n и m (1 ≤ n ≤ 10⁹ , 1 ≤ m ≤ 100 000) — требуемое 
количество цветов в букете и количество доступных видов цветов.
Каждая из следующих m строк описывает i-й вид цветов и содержит два целых числа a_i и b_i (0 ≤ a_i , b_i ≤ 10⁹ ) — увеличение счастья от первого цветка i-го вида и увеличение счастья от каждого последующего цветка этого вида.

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

Примеры

№	Входные данные	Выходные данные
1	4 3 5 0 1 4 2 2	14
2	5 3 5 2 4 2 3 1	16

Среди открытого банка задач ЕГЭ по математике есть следующая: по заданным натуральным числам l, r и m вас просят найти целые числа a, b и c, каждое из которых не меньше l и не больше r, и такие, что будет существовать натуральное число n (целое число, большее нуля) такое, что
n · a + b − c = m.
Паша еще только начал готовиться к ЕГЭ и не совсем понимает, как решать подобную задачу. Помогите ему для разных вариантов этой задачи находить подходящие a, b и c.

Формат входных данных
В единственной строке заданы три целых числа l, r и m (1 ≤ l ≤ r ≤ 500 000, 1 ≤ m ≤ 1010).

Формат выходных данных
Выведите три целых числа a, b и c такие, что l ≤ a, b, c ≤ r и существует такое натуральное число n, что n · a + b − c = m. Гарантируется, что такие числа существуют. Если подходящих решений несколько, выведите любое из них.
 

Примеры

№	Входные данные	Выходные данные
1	4 6 13	4 6 5
2	2 3 1	2 2 3

Замечание
В первом примере можно выбрать n = 3, тогда n · 4 + 6 − 5 = 13 = m. Так же возможны такие ответы: a = 4, b = 5, c = 4 (при этом n = 3); a = 5, b = 4, c = 6 (при этом n = 3); a = 6, b = 6, c = 5 (при этом n = 2); a = 6, b = 5, c = 4 (при этом n = 2).
Во втором примере n = 1, тогда n · 2 + 2 − 3 = 1 = m. Число n = 0 не могло быть выбрано, так как число n обязательно должно быть натуральным.

Сегодня Дима целый день старался и выписывал на длинную бумажную ленту своё любимое целое положительное число n, состоящее из l цифр. К сожалению, лента получилась настолько длинной, что в итоге не влезла в Димин шкаф.

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

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

Входные данные
Первая строка содержит одно целое число l (2 ≤ l ≤ 100000) — длину любимого числа Димы.

Вторая строка содержит целое положительное число n, изначально записанное на ленте — любимое число Димы.

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

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

Примечание
В первом примере Дима может разрезать число 1234567 на числа 1234 и 567. Их сумма равна 1801.

Во втором примере Дима может разрезать число 101 на числа 10 и 1. Их сумма равна 11.

Примеры

№	Входные данные	Выходные данные
1	7 1234567	1801
2	3 101	11

Наше счастье постоянно — жуй кокосы, ешь бананы, Жуй кокосы, ешь бананы, Чунга-чанга!
м/ф «Катерок»
После открытия острова «Чунга-Чанга» туда постепенно начала пробираться цивилизация и даже стала развиваться рыночная экономика. Появилась и новая валюта — чижик. Теперь для того, чтобы счастливо жевать кокосы, их нужно сначала купить под пальмой.

Саша и Маша проходили мимо пальмы, под которой продаются кокосы по цене z чижиков за штуку. У Саши есть x чижиков, а у Маши y. Каждая из девочек собирается купить максимальное число кокосов, на которое у неё хватит денег. Обсудив планы о покупке кокосов, девочки заметили, что если одна из них передаст какое-то количество чижиков другой, то суммарное количество кокосов, которое они купят, может от этого увеличиться (а может и уменьшиться). Кокосы не продаются по частям, то есть каждая из девочек может купить только целое неотрицательное число кокосов. Чижики тоже не могут быть разделены на части, то есть одна из девочек может передать другой только целое неотрицательное число чижиков.

Например, предположим, что у Саши было 5 чижиков, у Маши 4, а один кокос стоит 3 чижика. Тогда, если девочки не будут обмениваться чижиками, то они купят 1+1=2 кокоса. Если же Маша передаст Саше один чижик, то у Саши их будет 6, а у Маши 3, и девочки купят 2+1=3 кокоса.

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

Входные данные
Первая строка содержит три целых числа x, y и z (0 ≤ x, y ≤ 10¹⁸ , 1 ≤ z ≤ 10¹⁸) — количество чижиков у Саши, количество чижиков у Маши и цена одного кокоса.

Выходные данные
Выведите два целых числа — максимальное суммарное количество кокосов, которое можно купить, и минимальное количество чижиков, которым для этого придётся поделиться одной из девочек.
Примечание
Первый пример разобран в условии задачи. Во втором примере оптимально не обмениваться чижиками, в таком случае будет куплено 3+4=7 кокосов.

Примеры

№	Входные данные	Выходные данные
1	5 4 3	3 1
2	6 8 2	7 0

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

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

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

Входные данные
Первая строка входного файла содержит два целых числа: n и m (2 ≤ n, m ≤ 100). Каждая из последующих n строк содержит по m целых чисел a_i,j (|a_i,j| ≤ 100).

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

Описание каждого хода должно быть выведено в отдельной строке, которые должны содержать: тип хода («R» — на этом ходе выбирается строка или «C» — на этом ходе выбирается столбец) и номер соответствующей строки или столбца. Строки и столбцы нумеруются натуральными числами начиная с единицы, строки нумеруются сверху вниз, а столбцы — слева направо.

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

Примеры

№	Входные данные	Выходные данные
1	2 2 -1 -3 1 -2	1 C 2
2	3 2 -1 -1 -1 -1 -1 -1	3 R 1 R 2 R 3

Широко известна следующая задача для младших школьников. Три черепахи ползут по дороге. Одна черепаха говорит: “Впереди меня две черепахи”. Другая черепаха говорит: “Позади меня две черепахи”. Третья черепаха говорит: “Впереди меня две черепахи и позади меня две черепахи”. Как такое может быть? Ответ: третья черепаха врет!

По дороге одна за другой движутся N черепах. Каждая черепаха говорит фразу вида: “Впереди меня a_i черепах, а позади меня b_i черепах”. Ваша задача определить самое большое количество черепах, которые могут говорить правду.

Входные данные
В первой строке вводится целое число N (1 ≤ N ≤ 10000) . Далее следуют N строк, содержащих целые числа ai и bi, по модулю не превосходящие 10000, описывающие высказывание i-ой черепахи.

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

Выходные данные
Выведите целое число M – максимальное количество черепах, которые могут говорить правду.
 

Примеры

№	Входные данные	Выходные данные
1	3 2 0 0 2 2 2	2

Дано верное равенство вида a₁+a₂+…+a_N=b₁+b₂+…b_M, где a₁,a₂,…,a_N, b₁,b₂,…,b_M – некоторые действительные (не обязательно целые) числа. Требуется «округлить» это равенство, т.е. получить новое верное равенство c₁+c₂+…+c_N=d₁+d₂+…+d_M, где c₁,c₂,…,c_N,d₁,d₂,…,d_M — целые числа, и при этом c₁ получено округлением числа a₁ до целого вверх или вниз (так, например, число 1.7 разрешается округлить как до 1, так и до 2), c₂ получено округлением a₂, …, c_N – округлением a_N, d₁ – округлением b₁, …, d_M – округлением b_M. Если какое-то из чисел в исходном равенстве было целым, оно должно остаться без изменений.

Входные данные
Во входном файле задано сначала число N, затем N чисел a₁, a₂, …, a_N, затем число M, затем числа b₁, b₂, …, b_M. Каждое число задается на отдельной строке. M и N – натуральные числа, не превышающие 1000. Остальные числа — вещественные, каждое из них по модулю не превышает 1000 и содержит не более 6 цифр после десятичной точки. При этом a₁+a₂+…+a_N=b₁+b₂+…b_M.

Выходные данные
Если «округлить» равенство можно, то в выходной файл выведите сначала числа c₁,c₂,…,c_N, а затем числа d₁,d₂,…,d_M. Все числа должны быть целыми и выведены без десятичной точки. Числа должны разделяться пробелами или переводами строки. Если решений несколько, выведите любое из них.

Если округлить исходное равенство до верного целочисленного равенства невозможно, выведите одно число 0.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 0.15 -3.000 2.7 1 -0.15	1 -3 2 0	Обратите внимание, что число –3 может округляться только в –3, в то время как 0.15 можно округлить как до 0, так и до 1, 2.7 – до 2 или до 3, –0.15 – до –1 или до 0. Приведенное решение не является единственным: так же верным является, например, такое округление: 1+(–3)+2=0
2	2 1.7 2.5 3 1 2.000 1.20	2 2 1 2 1	Приведенное решение 1+3=1+2+1 не является единственным. Верными ответами также являются 2+2=1+2+1 и 2+3=1+2+2.
3	1 0.5 1 0.5	0 0	Здесь верными являются как ответ 1=1, так и 0=0.

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

Масса ювелирного изделия, которую нужно определить ювелиру, является целым числом от 1 до N. Ювелир должен запасти набор гирек (их массы также должны быть целыми числами), используя которые ювелир может определить любую возможную массу от 1 до N. Для определения массы ювелир может производить любое число взвешиваний, может использовать все гирьки или только некоторые из них, может класть гирьки на разные чашки весов.

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

Программа получает на вход натуральное число N (2 ≤ N ≤ 10⁸) – максимально допустимую массу ювелирного изделия.

Программа должна вывести несколько натуральных чисел, не превосходящих 10⁹, – массы гирек в минимальном требуемом для решения задачи наборе (допускается использовать гирьки массой, больше, чем N, если их масса не превосходит 10⁹).

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3	2	Пусть x – изделие, массу которого необходимо определить. Нужно на одну чашу весов положить x, а на другую чашу весов – гирьку в 2. Если x будет легче, то x = 1, при равенстве – x = 2, если x тяжелее, то x = 3.
2	5	3 4	Покажем, как при помощи гирек в 3 и 4 определить все массы от 1 до 5. Массы 3 и 4 можно определить при помощи равенств x = 3 и x = 4. Массу 1 можно определить при помощи равенства x + 3 = 4 (на одну чашу кладется изделие и гирька массой 3, на другую чашу – гирька массой 4). Массу 2 можно определить, например, по условию x < 3 (на одну чашу весов кладется изделие, на другую – гирька массой 3), а также проверив при помощи ранее описанного алгоритма, что x ≠ 1 . Массу 5 можно определить при помощи взвешивания x > 4.

Мы все знаем, что начавшаяся зима скоро закончится, и на праздновании Масленицы все будут есть блины. Об этом и будет наша задача.

N гостей сидят за столом, и перед каждым стоит тарелка с блинами. На тарелке i-го гостя лежит ai блинов. Каждый гость съедает один блин за одну минуту, таким образом, время, когда закончит есть блины последний человек, равно наибольшему значению из ai.

Неожиданно к ним присоединился ещё один человек, и теперь все присутствующие могут переложить часть своих блинов (в том числе могут переложить все свои блины, а могут не перекладывать ни одного блина) вновь пришедшему человеку. Перекладывание блинов происходит одновременно и моментально.

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

Программа получает на вход натуральное число N, не превосходящее 100.000, – первоначальное количество гостей. Следующие N строк содержат натуральные числа a_i – количество блинов на тарелке i-го человека. Значения a_i даны в порядке неубывания, то есть a_i ≤ a_i+1. Сумма значений всех a_i не превосходит 2·10⁹.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 1 3 5 6	4	За столом сидят 4 человека, у них на тарелках 1, 3, 5, 6 блинов. Новому гостю последний гость отдаст 2 блина, а предпоследний – 1 блин, и тогда у всех, включая нового гостя, будет не более 4 блинов.