Информатика

В этой задаче, как и в задаче B, Петя снова собирает своего M-лапого Зверя на прогулку (однако количество лап у Зверя в этой задаче может быть до 1000). Снова ему мама оставила N штанов, имеющих соответственно K₁, K₂, …, K_N штанин. Однако тетерь Петя хочет надеть на Зверя штаны так, чтобы выполнялись следующие условия:

• на каждой лапе была надета хотя бы одна штанина (гарантируется, что это всегда возможно),
• количество штанин, надетых на самую «утепленную» лапу, должно как можно меньше отличаться от количества штанин, надетых на самую легко одетую лапу (когда количество штанов, одетых на разные лапы, сильно отличается, Зверь испытывает дискомфорт),
• в отличие от задачи B Петя не обязан надеть на Зверя все имеющиеся штаны — какие-то из них можно оставить дома.

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

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

Входные данные
Вводится сначала число M, а затем число N (1 ≤ M ≤ 1000, 1 ≤ N ≤ 100). Далее вводятся N чисел Ki, обозначающих число штанин у оставленных мамой штанов (1 ≤ K_i ≤ M). Сумма всех Ki не меньше, чем M.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 3 1 2 3	1 1 1 1	Первые штаны надеты на лапу 1; вторые штаны не используем; третьи штаны надеты на лапы 2, 3 и 4. Таким образом, на всех лапах по 1 штанине.
2	4 2 3 2	2 1 1 1	Первые штаны надеты на лапы 1, 2 и 3; вторые штаны надеты на лапы 1 и 4. Таким образом, количество штанов на самой «утепленной» лапе (это лапа номер 1) – 2, а на остальных лапах по одной штанине, т.е. количество штанин на разных лапах отличается на один. Нетрудно заметить, что в этом примере нельзя одеть зверя так, чтобы на всех лапах было поровну штанин, поэтому этот ответ является оптимальным.

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

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

• сколько угодно раз напечатать сообщение X
• разобрать хитроумное устройство и посимвольно напечатать еще что-нибудь (назовем это Y)
• оторвать и выбросить начало ленты так, чтобы на оставшейся ленте было напечатано в точности сообщение Z

Поскольку набирать отдельные символы сообщения Y довольно сложно, Петя хочет, чтобы в сообщении Y было как можно меньше символов.

Для лучшего понимания задачи смотрите примеры и пояснения к ним.

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

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	mama amamam	m	Сначала Петя два раза напечатает слово mama, потом к нему припечатает букву m, а затем отрежет и выбросит три начальных символа (mam). Ответом является допечатываемая отдельно буква m.
2	ura mura	mura	Казалось бы, Пете стоит сначала напечатать букву m, а затем слово ura, которое он умеет печатать. Однако для того, чтобы напечатать m, ему придется разобрать свое устройство, и печатать ura ему придется также посимвольно.
3	computer comp	comp	Казалось бы, Петя может напечатать слово computer, а затем отрезать и выбросить его конец — однако он не может так поступить, потому что отрезать и выбросить он может только начало ленты.
4	ejudge judge		Пете достаточно один раз напечатать слово ejudge, а затем отрезать и выбросить букву e. Ничего посимвольно выводить ему не придется, поэтому ответом является пустая строка.
5	m mmm		Достаточно трижды напечатать исходное слово и нужный результат будет получен. Ничего добавлять не надо, поэтому ответ – пустая строка.

Как известно, обычно штаны состоят из двух штанин. Однако собачке нужны, например, уже штаны из 5 штанин (для 4-х лап и хвоста), а сороконожке – штаны с 40 штанинами.

У Пети живет Зверь, у которого M лап. Иногда – когда на улице особенно холодно, чтобы Зверь не простудился, на него бывает нужно надеть несколько штанов, чтобы на каждой лапе было надето по несколько штанин.

Петина мама оставила Пете N штанов, имеющих соответственно K₁, K₂, …, K_N штанин, наказав ему надеть на Зверя их все. Петя хочет надеть на Зверя штаны так, чтобы на самой «утепленной» лапе оказалось как можно меньше штанин, но при этом все оставленные мамой штаны были надеты на зверя. Любые штаны можно надевать на любой набор лап (каждая лапа встречается в наборе не более одного раза).

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

Входные данные
Вводится сначала число M, а затем число N (1 ≤ M ≤ 100, 1 ≤ N ≤ 100). Далее вводятся N чисел K_i, обозначающих число штанин у оставленных мамой штанов (1 ≤ K_i ≤ M).

Выходные данные
Выведите N строк, в i-ой строке должно быть выведено Ki различных чисел, обозначающих номера лап Зверя, на которые должны быть надеты штанины i-ых штанов. Лапы Зверя нумеруются натуральными числами от 1 до M. Если искомых ответов несколько, то выведите любой из них.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 3 1 2 3	1 1 2 2 3 4	Первые штаны надеты на лапу 1; вторые штаны надеты на лапы 1 и 2; третьи штаны надеты на лапы 2, 3 и 4. Таким образом, на самых «утепленных» лапах (а это лапы 1 и 2) надето по 2 штанины.
2	4 2 3 2	1 2 3 4 1	Первые штаны надеты на лапы 1, 2 и 3; вторые штаны надеты на лапы 1 и 4. Таким образом, количество штанов на самой «утепленной» лапе (это лапа номер 1) – 2.

Последовательность чисел a1, a2, …, ai,… называется Фибоначчиевой, если для всех i >= 3 верно, что ai = ai–1 + ai–2, то есть каждый член последовательности (начиная с третьего) равен сумме двух предыдущих. Ясно, что задавая различные числа a1 и a2 мы можем получать различные такие последовательности, и любая Фибоначчиева последовательность однозначно задается двумя своими первыми членами.

Будем решать обратную задачу. Вам будет дано число N и два члена последовательности: aN и aN+1. Вам нужно написать программу, которая по их значениям найдет a1 и a2.


Входные данные
Вводятся число N и значения двух членов последователности: aN и aN+1 (1 <= N <= 30, члены последовательности - целые числа, по модулю не превышающие 100).
Если вы пишите на языке программирования Python, то считывание aN и aN+1 элементов должно быть организовано так: 
x, y = map(int, input().split()).

Выходные данные
Выведите два числа — значения первого и второго членов этой последовательности.

Примеры

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

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

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

Входные данные
Во входном файле содержится сначала целое число N — количество деревьев (1 ≤ N ≤ 200). Затем идет N троек чисел, задающих деревья. Первые два числа задают координаты центра, а третье — радиус. Все данные задаются точно, и выражаются вещественными числами, не более чем с 2 знаками после десятичной точки, по модулю не превосходящими 1000.

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

Примеры

№	Входные данные	Выходные данные
1	3  0.00 30.00 25.00  0.00 -30.00 25.00  40.00 0.00 16.00	NO -833.3333340000 -552.7707973875  833.3333340000 552.7707973875
2	3 0.00 30.00 29.00 0.00 -30.00 29.00 40.00 0.00 19.00	YES

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

Вам дана полоса длины N. Требуется разрезать ее на полоски, являющиеся палиндромами, так, чтобы количество получившихся полосок было строго меньше величины (2/5)N + 3.

Входные данные
Первая строка входного файла содержит число N — длину исходной полосы (N — натуральное число, не превышающее 100000). Далее идет N чисел, описывающих раскраску полосы: 0 означает черную клетку, а 1 — белую.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	6 0 1 0 1 1 0	3 5	Из исходной полосы мы получим 3 полосы-палиндрома, сделав разрезы после 3-й клетки (то есть между 3-й и 4-й) и после 5-й (то есть между 5-й и 6-й)
2	6 0 1 1 0 0 0	1 3	Данную полосу можно разрезать на 2 полосы-палиндрома, однако по условию не требуется искать решение с минимальным числом получившихся полосок — достаточно, чтобы число полосок удовлетворяло указанному в условии ограничению.
3	5 0 0 0 0 0		Исходная строка уже является палиндромом, поэтому можно ничего не разрезать

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

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

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

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

Входные данные
Первая строка входного файла содержит одно число N (1≤N≤5000). В каждой из следующих N строк записано по 2 числа, вычисленных по Петиным законам для соответствующего дня — сколько рублей будет стоить 1 доллар, и сколько рублей будет стоить 1 евро. Все эти значения не меньше 0.01 и не больше 10000. Значения заданы точно и выражаются вещественными числами не более, чем с двумя знаками после десятичной точки.

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

Примеры

№	Входные данные	Выходные данные
1	1 30.00 9999.99	100.00

У калькулятора есть две ячейки памяти: содержимое первой из них всегда отображается на табло, вторая является буфером. В начальный момент времени на табло калькулятора отображается целое число X, а в буфере записано число 0. У калькулятора работают только две клавиши: «+» и «=». При нажатии на «+» число, которое в данный момент отображено на табло, копируется в буфер. При нажатии на «=» число из буфера прибавляется к числу, отображенному на табло и результат отображается на табло, число в буфере при этом не меняется.

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

Входные данные
Входной файл содержит два целых числа X и Y. Каждое из этих чисел по модулю не превышает 10⁹.

Выходные данные
В первую строку выходного файла выведите одно число — количество нажатий клавиш, которое потребуется для получения числа Y. Если из числа X получить число Y с помощью указанных операций невозможно, в выходной файл выведите одно число –1.

Примеры

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

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

Входные данные
Во входном файле записаны сначала числа N — количество станций (2 ≤ N ≤ 100) и E — количество пар станций, расстояния между которыми заданы (0 ≤ E ≤ 10000). Далее идет E троек чисел, первые два числа каждой тройки задают номера станций (это числа из диапазона от 1 до N), а третье — расстояние между этими станциями (все эти расстояния заданы точно и выражаются вещественными неотрицательными числами не более чем с 3-я знаками после десятичной точки).

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

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

Примеры

№	Входные данные	Выходные данные
1	2 3 1 1 0 2 2 0 2 1 2.5	1 2.500
2	15 13 1 2 1 1 3 2 1 4 3 1 5 4 1 6 5 1 7 6 1 8 7 1 9 8 1 10 9 1 11 10 1 12 11 1 13 12 15 14 13	2

Вася и Петя играют в следующую игру. Они берут колоду из 36 карточек. На каждой карточке написано число от 1 до 9 и каждая карточка покрашена в один из 4 цветов так, что есть ровно по 9 карточек каждого цвета, и они пронумерованы числами от 1 до 9. Карты перемешиваются, и игрокам раздается по несколько (не более чем по 18) карточек.

Дальше игроки по очереди делают ходы. За один ход игрок может выложить на стол одну или последовательно несколько карточек по следующим правилам. Карточку с цифрой 5 любого цвета можно выкладывать на стол без дополнительных условий. Карточку с другой цифрой можно выкладывать только если на стол уже выложена карточка того же цвета, на которой написано число на 1 большее или на 1 меньшее, чем на данной, или же карточка с той же цифрой, но другого цвета (не важно, была ли эта карточка выложена вами или вашим противником, и была ли она выложена на предыдущем ходе или раньше). Если ни одну карточку игрок выложить не может, он пропускает ход.

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

Входные данные
Во входном файле записано сначала число K — количество уже выложенных на стол карточек. Далее идет K пар чисел, описывающих эти карточки. Затем записано число N — количество карточек на руках у игрока, который сейчас должен делать ход. Далее записано N пар чисел, описывающих эти карточки.

Каждая карточка описывается двумя числами — номером цвета (от 1 до 4) и цифрой, которая написана на карточке (от 1 до 9).

Ограничения: 0≤K≤35, 1≤N≤36, N+K≤36, все карточки различны.

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

Примеры

№	Входные данные	Выходные данные	Комментарии
1	2 1 5 1 4 3 1 3 1 6 2 8	2	Это карты 1 3 (потому что на столе есть 1 4) и 1 6 (потому что на столе есть 1 5)
2	0 4 2 8 1 5 3 6 1 6	3	Первым ходом можно выложить 1 5, после этого мы имеем право выложить и 1 6, после которой выкладываем 3 6
3	3 1 4  1 5 1 6 2 2 8 2 9	0	Нельзя выложить ни одной карточки

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

Входные данные
Во входных данных записано сначала число N (2≤N≤100) – количество остановок на маршруте. Далее задается количество человек, севших в автобус на конечной. Далее идет (N-2) пары чисел, задающих для промежуточных остановок количество вышедших и количество вошедших пассажиров. Наконец, идет число, задающее количество вышедших из автобуса на конечной остановке.

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

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 10 3 1 5 10 0 2 15	15	На конечной в автобус село 10 человек. Далее 3 вышло и 1 зашел. В автобусе стало 8 человек. На следующей остановке вышло 5 и зашло 10. Стало 13 человек. На последней промежуточной остановке никто не вышел, а зашло 2 человека. На конечной вышло 15 человек. Итого максимальное количество – 15.
2	5 10 10 0 0 0 0 10 10	10	На конечной село 10 человек, которые на следующей остановке вышли. После этого на следующей остановке никто не сел и никто не вышел. Дальше опять село 10 человек, которые доехали до конечной.
3	5 0  0 9 3 4 2 0 8	10	С конечной автобус отправился без пассажиров. Дальше в него село 9 человек. На следующей остановке 3 вышли и зашли 4. В автобусе стало 10 человек. На следующей остановке 2 вышли и никто не зашел. 8 человек доехало до конечной. Максимальное количество пассажиров составляло 10
4	3 100 0 100 200	200	На начальной и на промежуточной остановку в автобус село по 100 человек. Вышло из автобуса 200 человек.

У Васи в распоряжении оказался набор кубиков. Вася решил на каждой грани каждого кубика написать по цифре и дальше использовать кубики для того, чтобы складывать из них числа. Вася хочет написать цифры так, чтобы уметь складывать любое число от 1 до некоторого числа K. Посчитайте такое максимальное K, до которого Вася сможет выкладывать все числа, если в распоряжении у Васи оказалось N кубиков. Заметьте, что если на какой-то грани какого-то кубика написана цифра 6, то эту же грань можно использовать и как цифру 9, просто перевернув соответствующий кубик.

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

Рассмотрим примеры.

Пусть N=1. Тогда, написав на гранях кубика цифры от 1 до 6, Вася сможет выкладывать числа от 1 до 6. Тем самым, K=6.

Пусть N=2. Тогда, написав на гранях одного кубика цифры от 1 до 6, а на гранях другого цифры 0, 1, 2, 3, 7, 8, Вася сможет выложить любое число от 1 до 43.

Входные данные
Во входных данных записано одно число N (1≤N≤1000000).

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

Примеры

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

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

Входные данные
Во входном файле записано сначала число N — количество городов (1≤N≤1000). Затем записано число M — количество дорог (1≤M≤100000). Далее идет M пар чисел, задающих дороги (каждая дорога описывается номерами городов, которые она соединяет). Не бывает дорог из некоторого города в тот же город. Между двумя городами может быть несколько дорог. Гарантируется, что до введения одностороннего движения можно было попасть из любого города в любой другой.

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

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

Примеры

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

На новой станции метро, которую планируют открыть в конце этого года, будет N эскалаторов (эскалаторы пронумерованы подряд числами от 1 до N). Эскалаторы имеют длину L и расположены на расстоянии H друг от друга. Шириной эскалатором пренебрежем. Между каждыми двумя соседними эскалаторами (точно посередине) будет установлен ряд ламп. В ряду будет K ламп. Лампы устанавливаются по следующему принципу: всю длину эскалатора L разбивают на K равных отрезков и в середине каждого отрезка устанавливают по лампе (см. рисунок). Всего будет установлено (N–1)*K ламп.


На приведенном рисунке N=4 (эскалаторы показаны жирными <горизонтальными линиями), L=20, H=4, K=5.

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

Входные данные
Во входном файле записаны числа N, L, H, K, J. Все числа — натуральные. 2≤N≤35, 1≤L≤1000, 1≤H≤1000, 1≤K≤35, 1≤J≤N.

Выходные данные
В выходной файл выведите одно число — ответ задачи.

Примеры

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

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

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

Если останется одна кучка, то Вася все конфеты съест сам, а если две — то конфеты из первой кучки он съест сам, а из второй кучки отдаст Пете.

Напишите программу, которая по исходному распределению конфет в кучках определит, чем закончится Васина игра.

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

Во входном файле задано сначала число K (1≤K≤10⁵). Затем идет K пар чисел Ai, Ni (1≤A_i≤100, 1≤N_i≤10⁸). Общее количество кучек так же не превысит 10⁸.

Выходные данные
В выходной файл выведите сначала 1 или 2 — количество кучек конфет, которые останутся в конце игры. Затем выведите соответственно одно или два числа — количества конфет в оставшихся кучках.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 2 2 3 2 2 1	2 11 1	Исходно конфеты расположены в следующих кучках: 2 кучки по 2 конфеты, две кучки из 3-х конфет и одна из 2-х: 2 2 3 3 2 Далее по 2 конфеты перекладывается из 1 и 5кучек во 2 и 4, при этом и 1 и 5 кучки становятся пустыми, т.е. на столе остается только 3 кучки: 4 3 5 Теперь по 4 конфеты перекладываются из 1 и 3 кучек во 2-ю и на столе остается две кучки, игра заканчивается с результатом 11 1
2	1 1 7	1 7	Изначальноу нас 7 кучек по 1 конфете в каждой. После первого перекладывания получится следующая конфигурация: 2 1 1 1 1 2 После второго: 3 1 3 После третьего останется одна кучка с 7 конфетами.
3	5 1 1 2 1 3 1 4 1 5 2	2 15 5	Изначально имеется 6 кучек: 1 2 3 4 5 5 После первого перекладывания получим: 3 3 4 6 4 После второго: 6 4 9 1 После третьего: 5 5 10 Наконец, получим: 15 5

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

Правила вычисления выражения, рассказанные ученику, звучат так. Если в выражении вообще нет скобок, то сначала выполняются все операции умножения слева направо, а затем — операции сложения также слева направо. Если же в выражении есть скобки, то находится самая левая пара скобок (открывающая и закрывающая), содержащая внутри себя бесскобочное выражение, которое может быть вычислено по вышеописанным правилам. Дальше это выражение (вместе со скобками) мысленно удаляется из выражения и заменяется числом – результатом. Если в выражении остались скобки, то процедура повторяется.

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

Входные данные
Во входном файле записана одна строка, состоящая из символов #, +, *, (, ). Длина строки не превышает 250 символов. Строка соответствует правильному арифметическому выражению.

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

Примеры

№	Входные данные	Выходные данные
1	#+#*#	#2#1#
2	#+#+(#+#)	#2#3(#1#)
3	#+(#+#*#)*#+#	#4(#2#1#)3#5#
4	#+#+#+#+#+#+#+#+#+#+#	#1#2#3#4#5#6#7#8#9#10#
5	#+#+(#+(#+#))+(#+#)	#4#5(#2(#1#))6(#3#)

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

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

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

Входные данные
В первой строке входного файла записано число N — длина исходной последовательности (1≤N≤1000). Во второй строке идет сама последовательность. Последовательность состоит только из заглавных латинских букв.

Выходные данные
В выходной файл выведите выигрышную последовательность.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 MAMA	A	Рассматриваются строки MAMA, AMA, MA, A. Выигрышная строка A
2	4 ALLO	ALLO	Выигрышной является исходная строка
3	5 BBABB	ABB

Напишите программу, которая по изображению поля для игры в «Крестики-нолики» определит, могла ли такая ситуация возникнуть в результате игры с соблюдением всех правил.

Напомним, что игра в «Крестики-нолики» ведется на поле 3×3. Два игрока ходят по очереди. Первый ставит крестик, а второй – нолик. Ставить крестик и нолик разрешается в любую еще не занятую клетку поля. Когда один из игроков поставит три своих знака в одной горизонтали, вертикали или диагонали, или когда все клетки поля окажутся заняты, игра заканчивается.

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

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

Примеры

№	Входные данные	Выходные данные
1	1 1 1 1 1 1 1 1 1	NO
2	2 1 1 1 1 2 2 2 1	YES
3	1 1 1 2 0 2 0 0 0	YES
4	0 0 0 0 1 0 0 0 0	YES
5	1 1 1 2 2 2 0 0 0	NO

В игре Cookie Clicker игрок зарабатывает печеньки (cookies), щёлкая мышкой по изображению большой печеньки. Тратя заработанные печеньки, игрок может покупать различные усовершенствования (ферму, фабрику и т. д.), которые также производят дополнительные печеньки.

Рассмотрим упрощённый вариант этой игры. Пусть игрок может сделать один щелчок мышкой в секунду, что приносит ему одну печеньку. Также в любой момент времени игрок может потратить C печенек на покупку фабрики (при этом у игрока должно быть не меньше C печенек, после покупки фабрики количество его печенек моментально уменьшается на C ). Каждая купленная фабрика увеличивает ежесекундное производство печенек на P штук (то есть если у игрока одна фабрика, то он получает 1  + P печенек в секунду, две фабрики — 1  +  2 P печенек, три фабрики — 1  +  3 P печенек и т. д.). Игрок может приобрести неограниченное число фабрик стоимостью C печенек каждая. Фабрика начинает производить дополнительные печеньки сразу же, например, если после какой-то секунды игры у игрока стало C печенек, то игрок может купить фабрику и уже на следующей секунде его производство печенек увеличится на P штук.

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

Входные данные
Программа получает на вход три целых положительных числа, записанных в отдельных строках: С (стоимость фабрики), P (производительность одной фабрики) и N (необходимое количество печенек).

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	50 3 100	75	Через 50 секунд после начала игры у игрока будет 50 печенек, и он сможет купить фабрику. После этого он будет получать 4 печеньки в секунду, и на производство 100 печенек понадобится еще 25 секунд.
2	99 10 100	100	Игрок сможет набрать 100 печенек за 100 секунд, при этом фабрику покупать нет смысла.

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

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


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

Выходные данные
Программа получает на вход два числа N и M, записанные в отдельных строках, — количество строк и столбцов карты острова (3 ≤ N ≤ 100, 3 ≤ M ≤ 100). Далее записана карта острова — N строк, каждая содержащая M символов. Каждый символ карты может быть либо символом «.», что означает клетку, не принадлежащую острову, либо символом «#», что означает клетку острова. При этом остров не касается края карты.

Введём на карте систему координат. Первая координата является номером строки, строки нумеруются сверху вниз числами от 1 до N. Вторая координата — номер столбца, столбцы нумеруются слева направо числами от 1 до M.

Входные данные
Программа должна вывести координаты клеток карты в порядке их облёта самолётом. Каждая строка вывода должна содержать два числа x и y — координаты самолёта, записанные через пробел (1 ≤ x ≤ N, 1 ≤ y ≤ M). Самолёт должен побывать в каждой соседней с островом клетке ровно один раз. Каждые две клетки, идущие подряд в выводе, должны иметь общую сторону. Можно вывести любой возможный маршрут облёта острова.

Примеры

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