Язык программирования

Робот перемещается по клетчатой плоскости и рисует спираль. Исходно он находится в клетке (0, 0) и направлен в сторону увеличения первой координаты.
Далее он действует по следующему алгоритму: совершает d перемещений вперед, затем поворачивает налево и снова делает d перемещений вперед. После этого он поворачивает налево и умножает значение d на k. Затем робот повторяет описанный процесс. Робот останавливается, сделав суммарно ровно n перемещений.
Требуется вывести картинку, на которой отмечены клетки, на которых побывал робот.

Входные данные
На вход подаются целые числа n, d и k (1 ≤ n ≤ 1000, 1 ≤ d ≤ 100, 2 ≤ k ≤ 5).

Выходные данные
Пусть минимальный прямоугольник из клеток, содержащий все посещенные роботом клетки, имеет высоту h и ширину w. На первой строке выведите числа h и w, разделенные пробелом. Следующие h строк должны содержать по w символов, выведите «*» для клетки, посещенной роботом и «.» для не посещенной.

Примеры

№	Входные данные	Выходные данные
1	13 2 2	5 5 ***** *...* *.*** *.... **...

Для борьбы с могучими рейнджерами Рита Репульса и Лорд Зедд решили объединить Глиняный и Зедд патрули. Для более эффективного нападения на Энджел Гроув они хотят построить свою армию в две шеренги. Количество солдат в первой шеренге равно количеству солдат во второй.
Рита любит два вопроса:

•  «Правда ли, что ровно x из твоих соседей из Зедд патруля?»
•  «Правда ли, что ровно y из твоих соседей из Глиняного патруля?»

Соседями в данном построении являются солдаты слева и справа в той же шеренге, а также солдат, который стоит на той же позиции, но в другой шеренге. Рита выбрала либо один из этих вопросов либо оба, и задала каждому солдату. Всем солдатам были заданы вопросы с одними и теми же значениями x и/или y.
Зордан с помощью своей магической силы все это время наблюдал за процессом построения. Он был очень удивлен тем, что ответы всех солдат были положительными. Однако, он помнит, что солдаты из Зедд патруля всегда говорят правду, а солдаты из Глиняного патруля обязательно солгут хотя бы на один вопрос.
Так как солдаты из Зедд патруля наиболее опасны по мнению Зордана, исходя из ответов, он хочет узнать какое наименьшее и наибольшее количество солдат из Зедд патруля могло быть в объединенной армии. Он обратился к вам за помощью!

Входные данные
В единственной строке входного файла содержатся три целых числа k, x, y — количество солдат в одной шеренге и числа из вопросов (1 ≤ k ≤ 10⁵; -1 ≤ x, y ≤ 3).
Если x = -1, это означает, что Рита не задавала первый вопрос.
Если y = -1, это означает, что Рита не задавала второй вопрос.
Гарантируется, что Рита задала хотя бы один вопрос.

Выходные данные
Если для данных k, x и y не существует ни одного способа построения, выведите -1.
Иначе, первая строка выходного файла должна содержать одно число — наименьшее возможное количество солдат из Зедд патруля в армии.
В следующих двух строках должно содержаться по k символов «0» и «1» — описание шеренг:

•  «0» означает, что в построении на соответствующей позиции стоит солдат из Глиняного патруля.
•  «1» — солдат из Зедд патруля.

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

Примеры

№	Входные данные	Выходные данные
1	2 0 -1	2 01 10 2 01 10
2	5 1 2	0 00000 00000 4 01010 01010
3	1 2 2	0 0 0 0 0 0
4	10 0 3	5 0100010010 0001000100 8 0101010100 0010101010

Мегазорд — необходимая вещь для защиты Земли. Для сборки одного мегазорда, необходимо ровно три зорда: зеленый, красный и синий.
Зеленому, красному и синему рейнджеру стало интересно, сколько у них есть различных способов собрать мегазорд. Для каждого рейнджера известен набор зордов, которыми он обладает. У зеленого рейнджера есть зеленые зорды, у красного рейнджера — красные, а у синего — синие.
При сборке мегазорда необходимо соблюдать три правила:

•  Первая цифра номера модели красного зорда должна быть равна последней цифре модели зеленого.
•  Последняя цифра номера модели красного зорда должна быть равна первой цифре модели синего.
•  Все три использованных зорда должны иметь разные номера моделей.

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

Входные данные
В первой строке входного файла заданы числа g, r и b — количество зордов у зеленого, красного и синего рейнджера соответственно (1 ≤ g, r, b ≤ 10⁵).
В следующей строке находится g чисел x_i — номера моделей, которые есть у зеленого рейнджера (0 ≤ x_i ≤ 10⁹).
В следующей строке находится r чисел y_i — номера моделей, которые есть у красного рейнджера (0 ≤ y_i ≤ 10⁹).
В следующей строке находится b чисел z_i — номера моделей, которые есть у синего рейнджера (0 ≤ z_i ≤ 10⁹).

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

Примеры

№	Входные данные	Выходные данные
1	3 3 2 101 11 52 11 23 23 31 13	3

Замечание
Различные мегазорды из первого примера: 101 + 11 + 13, 52 + 23 + 31, 52 + 23 + 31. Последний мегазорд встречается дважды, так как красный ренжер мог взять либо второй, либо третий зорд. Обратите внимание, что собрать мегазорд 11+11+13 нельзя, так как при этом одна и та же модель будет использована дважны.

Не каждый день могучие рейнджеры надевают свои костюмы. Сами посудите: как нелепо они бы смотрелись, скажем, в общественном транспорте, если бы не снимали их!
Это создаёт определённые трудности злодеям, которые хотят выследить их. Вот и сегодня Рита Репульса не может их поймать, потому что не знает, как они выглядят без костюмов.
Рита следит за автобусом, в котором, по её мнению, едет кто-то из рейнджеров. В салоне автобуса n рядов сидений, в каждом из которых по два места — слева и справа от прохода. Ряды пронумерованы от 1 до n, начиная с передней части автобуса. На конечной остановке в автобус по очереди зашли k человек, и Рита знает, кто на какое место сел и в каком порядке. Кроме того, ей известно, как каждый из рейнджеров выбирает себе место, когда заходит в автобус:

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

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

Входные данные
В первой строке заданы числа n и k — количество рядов в автобусе и количество пассажиров (1 ≤ n ≤ 10⁹, 1 ≤ k ≤ min(2 · 10⁵, 2n)).
В следующих k строках описаны пассажиры в том порядке, в котором они заходили в автобус.
В i-й из этих строк заданы числа x_i и y_i — место, на которое сел i-й пассажир (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ 2), x_i — это номер ряда, y_i = 1, если это место слева от прохода, и y_i = 2, если справа.
Все места, на которые сели пассажиры, различны.

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

Примеры

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

Замечание

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

Склиссы — "сумчатые парнокопытные" в виде коровы с перепончатыми крыльями с планеты Шешинеру. Несмотря на способность летать, склисс, как и любая земная корова, достаточно ленива и тугодумна (почитайте побольше про склиссов ). 
Профессор Игорь Селезнев взял на борт трех склиссов для изучения: Бесси (Bessie), Элси (Elsie) и Милдред (Mildred), каждая из которых изначально дает 7 галлонов молока в день. Поскольку известно, что надой склисса со временем может измениться, профессор Селезнев проводит периодические измерения в течение следующих 100 дней и записывает их в журнал. Записи в его журнале выглядят так:

35 Bessie -2
14 Mildred +3

Первая запись указывает на то, что на 35-й день надой Бесси был на 2 галлона ниже, чем при последнем измерении. Следующая запись указывает, что на 14-й день надой молока у Милдред увеличился на 3 галлона по сравнению с тем, когда он был измерен в последний раз.
Профессор Селезнев занят во многих исследованиях, поэтому он может сделать не более одного измерения в день. К сожалению, он не всегда успевает сразу записать все в журнал и, поэтому его измерения могут идти не в хронологическом порядке.

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

Входные данные
Первая строка ввода содержит N, количество измерений, которые сделал профессор. Каждая из последуюших N строк описывает одно измерение, в формате, описанном выше: день (целое число от 1 до 100), имя склисса, и изменение производительности (ненулевое целое число). Количество молока, которое даёт любой склисс, всегда будет в интервале 0..1000.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 7 Mildred +3 4 Elsie -1 9 Mildred -1 1 Bessie +2	3	Иначально все склиссы дают по 7. В день 1 производительность Бесси вырастет до 9, делая её единственной победительницей и вынуждающей профессора сменить фотографию. В день 4 производительность Элси уменьшится до 6, но это не изменит того факта, что лидером останется Бэсси. В день 7 Милдред выйдет в лидеры, в день 8 Милдред сравняется с Бесси, что опять приведёт к смене карточек.

У Анны Николаевны есть N ящиков с конфетами. В i-м ящике лежит Ai количество конфет.  Анна Николаевна достает конфеты из нескольких последовательных коробок и равномерно раздает их M детям. Найдите количество пар (l, r), удовлетворяющих следующим условиям:
- l и r целые числа и удовлетворяют условию 1<=l<=r<=N;
- Al + Al+1 + ... + Ar делится на M.

Входные данные
Программа получает на вход две строки. Первая строка содержит два целых числа N (1<=N<=10⁵) и M (2<=M<=10⁹). Вторая строка содержит N чисел Ai (1<=A_i<=10⁹, 1<=i<=N).

Выходные данные
Выведите количество пар (l, r), удовлетворяющих условиям. Обратите внимание, что число может не соответствовать 32-битному целочисленному типу.
 

Примеры

№	Входные данные	Выходные данные
1	3 2 4 1 5	3
2	13 17 29 7 5 7 9 51 7 13 8 55 42 9 81	6

В хранилище Васи находится n объектов, пронумерованных от 1 до n, у каждого из которых есть некоторое количество свойств (возможно, ни одного). Каждое свойство представлено в виде натурального числа от 1 до 10⁹.
Проанализировав устройство своего хранилища, Вася решил, что оно должно поддерживать две операции:
 -  Удаление устаревшего свойства c. При удалении свойства, оно удаляется у всех объектов, которым принадлежит. Если указанного свойства не существует, ничего делать не нужно.
 -  Найти количество удаленных свойств у объекта r
Васе очень нужно реализовать эту функциональность, и он обратился к вам за помощью. Помогите ему - напишите программу, которая будет поддерживать обе операции, нужные Васе.

Входные данные
В первой строке входного файле содержится число n - количество объектов в хранилище Васи (1 <= n <= 10⁵). В i-й из следующих n строк содержится описание свойств объекта с номером i: сначала дано число k_i - количество свойств у i-го объекта, а затем через пробел даны k_i чисел pi,j - свойства i-го объекта (0 <= k_i <= 100, 1 <= p_i,j <= 10⁹).
Все объекты пронумерованы от 1 до n в порядке, представленном во входных данных. Гарантируется, что общее количество свойств у всех объектов не превосходит 10⁵. Также гарантируется, что для каждого i все pi,j различны.
В n + 2 строке содержится число q - количество запросов к хранилищу Васи (1 <= q <= 10⁵).
В j-й из следующих q строк содержится информация об j-м запросе:
- c, если из хранилища требуется удалить устаревшее свойство c (1 <= c <= 10⁹);
? r, если требуется найти количество оставшихся свойств у объекта с номером r.

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

Примеры

№	Входные данные	Выходные данные
1	2 3 1 2 4 3 2 3 5 12 - 1 ? 1 ? 2 - 2 ? 1 ? 2 - 5 ? 1 ? 2 - 6 ? 1 ? 2	1 0 2 1 2 2 2 2

Замечание

Свойство 1 есть только у первого объекта, поэтому после его удаления у первого объекта 1 удаленное свойство, а у второго все еще 0.
Свойство 2 есть у обоих объектов, поэтому оно удаляется у обоих объектов, у первого объекта теперь 2 удаленных свойства, а у второго 1.
Свойство 5 есть только у второго объекта, поэтому после его удаления у обоих объектов становится 2 удаленных свойства.
Свойства 6 нет ни у одного объекта, поэтому его удаление не меняет количество удаленных свойств у объектов.
 

В хранилище Васи находится n объектов, пронумерованных от 1 до n, у каждого из которых есть некоторое количество свойств (возможно, ни одного). Каждое свойство представлено в виде натурального числа от 1 до 10⁹.
Проанализировав устройство своего хранилища, Вася решил, что оно должно поддерживать две операции:
 -  Удаление устаревшего свойства c. При удалении свойства, оно удаляется у всех объектов, которым принадлежит.
Если указанного свойства не существует, ничего делать не нужно.
 -  Найти количество оставшихся свойств у объекта с номером r.
Васе очень нужно реализовать эту функциональность, и он обратился к вам за помощью. Помогите ему - напишите программу, которая будет поддерживать обе операции, нужные Васе.

Входные данные
В первой строке входного файле содержится число n - количество объектов в хранилище Васи (1 <= n <= 10⁵). В i-й из следующих n строк содержится описание свойств объекта с номером i: сначала дано число ki - количество свойств у i-го объекта, а затем через пробел даны ki чисел pi,j - свойства i-го объекта (0 <= k_i <= 100, 1 <= p_i,j <= 10⁹).
Все объекты пронумерованы от 1 до n в порядке, представленном во входных данных. Гарантируется, что общее количество свойств у всех объектов не превосходит 10⁵. Также гарантируется, что для каждого i все pi,j различны.
В n + 2 строке содержится число q - количество запросов к хранилищу Васи (1 <= q <= 10⁵).
В j-й из следующих q строк содержится информация об j-м запросе:
- c, если из хранилища требуется удалить устаревшее свойство c (1 <= c <= 10⁹);
? r, если требуется найти количество оставшихся свойств у объекта с номером r.

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

Примеры

№	Входные данные	Выходные данные
1	2 3 1 2 4 3 2 3 5 12 - 1 ? 1 ? 2 - 2 ? 1 ? 2 - 5 ? 1 ? 2 - 6 ? 1 ? 2	2 3 1 2 1 1 1 1

Замечание

Свойство 1 есть только у первого объекта, поэтому после его удаления у первого объекта остается 2 свойства, а у второго все еще 3.
Свойство 2 есть у обоих объектов, поэтому оно удаляется у обоих объектов, у первого объекта остается 1 свойство, а у второго - 2.
Свойство 5 есть только у второго объекта, поэтому после его удаления у обоих объектов остается 1 свойство.
Свойства 6 нет ни у одного объекта, поэтому его удаление не меняет количество свойств у объектов.
 

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

Входные данные
Программа получает на вход число элементов в генеалогическом древе N. Далее следует N−1 строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имя_потомка имя_родителя.

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

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

Пример

№	Входные данные	Выходные данные
1	9 Alexei Peter_I Anna Peter_I Elizabeth Peter_I Peter_II Alexei Peter_III Anna Paul_I Peter_III Alexander_I Paul_I Nicholaus_I Paul_I	Alexander_I 0 Alexei 1 Anna 4 Elizabeth 0 Nicholaus_I 0 Paul_I 2 Peter_I 8 Peter_II 0 Peter_III 3

Вите на день рождения подарили Очень Большую Игрушечную Железную Дорогу. Она представляет собой два параллельных пути, по которым движутся поезда во встречных направлениях. В центре находится станция, а железная дорога очень большая, поэтому можно считать пути бесконечными в обе стороны. Витя расставил поезда на железной дороге и одновременно запустил их, включив электропитание. Все поезда движутся с одинаковыми скоростями в одном из двух возможных направлений. Но когда-нибудь поезда придётся остановить и убрать игру, а поскольку поезд не может развернуться и начать движение в противоположном направлении, Вите придётся самому собирать поезда руками и переносить их на станцию. Витя хочет выбрать такой момент остановки всех поездов, чтобы ему пришлось потратить минимальное число усилий для того, чтобы собрать после этого все поезда на станции вместе, то есть в этот момент времени сумма расстояний всех поездов до станции была бы минимальной.

Входные данные
Введём на железной дороге координаты, считая, что станция находится в начале координат, а все поезда первоначально находятся в целочисленных точках координатной прямой. Сами поезда также будем считать точками. За одну секунду координаты всех поездов изменяются на +1 или на −1. Поезда движутся с равными скоростями, первоначально никакие два поезда, движущиеся в одном направлении, не находятся в одной точке. Первая строка входных данных содержит целое число N — количество поездов, движущихся в положительном направлении. Вторая строка входных данных содержит целое число M — количество поездов, движущихся в отрицательном направлении. Ограничения: N > 0, M > 0, 1 <= N + M <= 10⁵ . Следующие N строк содержат N чисел ai (|ai | <= 10⁹ ) — первоначальные координаты поездов, движущихся в положительном направлении. Все числа ai различны и заданы в порядке возрастания. Следующие M строк содержат M чисел bj (|bj | <= 10⁹ ) — первоначальные координаты поездов, движущихся в отрицательном направлении. Все числа bj различны и заданы в порядке возрастания.

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

Пример

№	Входные данные	Выходные данные	Пояснение
1	3 2 -5 -2 4 1 4	2	В примере из условия 3 поезда движутся в положительном направлении, 2 поезда движутся в отрицательном направлении. Начальные координаты поездов, движущихся в положительном направлении равны −5, −2, 4, движущихся в отрицательном направлении равны 1 и 4. Запишем, что при t = 0 координаты поездов (−5, −2, 4, 1, 4). Суммарное расстояние всех поездов до станции равно 16. В момент t = 1 координаты поездов будут (−4, −1, 5, 0, 3), суммарное расстояние до станции равно 13. В момент t = 2 координаты поездов будут (−3, 0, 6, −1, 2), суммарное расстояние до станции равно 12. В момент t = 3 координаты будут (−2, 1, 7, −2, 1), суммарное расстояние до станции равно 13. Ответ на этот тест t = 2.

Гриша уже несколько несколько недель отрабатывает свои навыки в новомодной онлайн-игре про команду космического корабля, вычисляющую предателей среди них. Так как игра очень популярна, появились игроки, которые договариваются между собой о каких-то способах коммуницировать заранее. Таких людей называют заговорщиками.
Заговорщики действуют по следующему алгоритму. В начале игры каждый из заговорщиков пишет в общий чат строку T — ключ шифрования. Далее в течение игры игрок придумывает строку S, записывает её N раз подряд и отправляет в чат. Для того, чтобы получить зашифрованное сообщение, остальным заговорщикам нужно посчитать, сколько раз в этой повторённой N раз строке S встречается ключ шифрования T. Чат обновляется слишком быстро и Гриша не успевает это сделать руками. Помогите Грише решить эту задачу.

Входные данные
В первой строке входных данных записана строка T, содержащая не более 300 символов — ключ шифрования. Во второй строке записана строка S, её длина также не превосходит 300. В третьей строке записано целое число N, 1 <= N <= 5 × 10⁶ — количество повторений строки S. Все строки состоят только из заглавных английских букв.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	MON AMONGUS 3	3
2	ABA BABA 3	5	Если строку BABA повторить 3 раза, получится BABABABABABA. В полученной строке подстрока ABA встречается 5 раз: BABABABABABA, BABABABABABA, BABABABABABA, BABABABABABA, BABABABABABA

Незнайка и его друг Гунька играют в игру. Игра состоит из N ходов. На каждом ходу каждый игрок играет одним из двух жестов, Камень и Бумага, как в «Камень-ножницы-бумага», при следующих условиях:
- После каждого хода
(количество раз, когда игрок играл Бумагу) <= (количество раз, когда игрок играл Камень).
- Счет каждого игрока рассчитывается по формуле:
(количество ходов, на которых игрок выигрывает) - (количество ходов, на которых игрок проигрывает),
где результат каждого хода определяется по правилам «камень-ножницы-бумага».

Для тех, кто не знаком с игрой "Камень-нужница-бумага": если один игрок играет Камень, а другой играет Бумагу, последний игрок выиграет, а первый проиграет. Если оба игрока играют одним и тем же жестом, раунд считается ничейным, и ни один из игроков ни выиграет ни проиграет.

Используя волшебную палочку Незнайка смог предвидеть жест, который Гунька будет использовать в каждом из N ходов перед началом игры. Распланируйте жесты Незнайки на каждом шагу, чтобы максимизировать его счет.
Жест, который Гунька будет воспроизводить на каждом ходу, задается строкой s. Если i-й (1 <= i <= N) символ в s равен g, то Гунька будет играть "Камень" на i-м ходу. Аналогично, если i-й (1 <= i <= N) символ s в p, Гунька будет играть Бумага на i-м ходу.

Входные данные
На вход подается одна строка s длиной N. Каждый символ в строке s - это g или p. Жесты, представленные s, удовлетворяют условию игры.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	gpg	0	Выполнение одного и того же жеста с противником на каждом этапе дает 0 очков, что является максимально возможным результатом.
2	ggppgggpgg	2	Например, рассмотрите возможность воспроизведения жестов в следующем порядке: Камень, Бумага, Камень, Бумага, Камень, Камень, Бумага, Бумага, Камень, Бумага. Эта стратегия приносит три победы и одно поражение, в результате чего получается 2, что является максимально возможным результатом.

Случилась беда — шпиона Сергея раскрыли, и теперь ему нужно срочно бежать! Но перед побегом он должен удалить все компрометирующие данные со своего компьютера.
На компьютере Сергея сохранены N файлов, пронумерованных числами от 1 до N. У каждого из файлов есть размер в байтах: a₁, a₂, . . . , a_N. Все данные на компьютере Сергея хорошо зашифрованы. Шпион определил, что для удаления файла с номером i понадобится минимум из a_i−1 и a_i+1 секунд (для удаления первого файла потребуется a₂ секунд, а для удаления последнего — a_N−1 секунд). Когда остается всего один файл, он удаляется мгновенно. После удаления файла с номером i остальные файлы перенумеровываются последовательно.
У Сергея осталось очень мало времени, а ему еще нужно собрать вещи, поэтому он просит у вас помощи. Определите, какое минимальное время понадобится шпиону, чтобы удалить все файлы.
Сергей может удалять файлы последовательно в любом порядке.

Входные данные
В первой строке выходных данных записано одно целое число N (1 ≤ N ≤ 10⁵) — количество файлов на компьютере шпиона.
В каждой из следующих N строк записано по одному целому числу a_i (1 ≤ a_i ≤ 10⁴) — размер файла с номером i на компьютере Сергея.

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

Примеры

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

Замечание
В первом примере у Сергея есть файлы с размерами 1, 2, 3, 1, 100. Один из вариантов решения приведен ниже:
1. Удалим последний файл. Это займет одну секунду.
2. Затем удалим файл размера 2 за одну секунду.
3. Далее удалим файл размера 3 за одну секунду.
4. Теперь удалим любой из оставшихся двух файлов за одну секунду.
5. Последний файл моментально удалится сам.
Итого, Сергею понадобится 1 + 1 + 1 + 1 = 4 секунды.
Во втором примере у Сергея изначально есть всего один файл, который сразу же удалится.
 

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

Входные данные
В первой строке входных данных записано целое неотрицательное число N (1 ≤ N ≤ 10⁹ ).
Во второй строке входных данных записано целое положительное число K (2 ≤ K ≤ 10⁹ ).

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

Примеры

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

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

Однажды после олимпиады по экономике Мише приснился очень красочный и необычный сон.
Мальчик оказался министром финансов Берляндии. Осознав свою значимость, он тут же решил произвести в стране реформу. Раньше в Берляндии использовались банкноты с номиналами 1, 10, 100 и 1 000 бурлей. Мише данная система показалась крайне банальной, поэтому он решил придумать что-то свое.
Мальчик выбрал два целых числа x и y (x ≤ y) и заявил, что теперь в Берляндии будут использоваться только банкноты с номиналами x, x + 1, x + 2, . . . , y бурлей. Вскоре реформа была принята и вступила в силу, однако населению страны это совсем не понравилось. Недовольства начались из-за того, что теперь, используя новые банкноты, можно было набрать далеко не любую сумму.
Например, если Мишей были выбраны числа x = 5 и y = 7, то невозможно набрать суммы 1, 2, 3 и 4 бурлей. Также не получится набрать суммы 8 и 9 бурлей. Если же выбрать числа x = y = 2, то невозможно будет набрать любую нечетную сумму.
Миша, находясь на грани увольнения, решил успокоить население Берляндии и предъявить такое минимальное число N, что при помощи новых банкнот возможно набрать любую сумму, начиная с N. Таким образом, должно быть возможно набрать суммы N бурлей, N + 1 бурлей, N + 2 бурлей, и так далее. Помогите Мише найти искомое число N и избежать увольнения.

Входные данные
В первой строке входных данных записано целое число x — минимальный номинал новых банкнот.
Во второй строке записано целое число y (1 ≤ x ≤ y ≤ 2 · 10⁹ ) — максимальный номинал новых банкнот.

Выходные данные
Выведите одно натуральное число N — минимальное число, такое, что при помощи банкнот с номиналами x, x + 1, x + 2, . . . , y можно набрать любую сумму, начиная с N бурлей. Если такого числа не существует, в качестве ответа выведите −1.

 
Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 7	10	Имеются банкноты трех номиналов: 5, 6 и 7 бурлей. Ниже перечислены суммы, которые можно набрать при помощи данных банкнот: • 5 = 5, • 6 = 6, • 7 = 7, • 10 = 5 + 5, • 11 = 5 + 6, • 12 = 5 + 7, • 13 = 6 + 7, • . . . Можно показать, что при помощи банкнот данных номиналов возможно набрать любую сумму, начиная с 10 бурлей.
2	2 2	-1	Есть банкноты всего одного номинала: 2 бурля. При помощи данных банкнот можно набрать только любую чётную сумму: 2, 4, 6, .... Таким образом, искомого числа N не существует.
3	1900000000 2000000000	36100000000

Горилла Коко очень любит путешествовать по своим родным джунглям с помощью лиан.
Всего в джунглях есть N лиан, расположенных друг за другом и пронумерованных слева направо целыми числами от 1 до N. Расстояние между соседними лианами составляет D метров. Находясь на i-й лиане, Коко может совершить прыжок с нее не более, чем на ai метров вправо. В процессе прыжка Коко должна зацепиться за какую-то другую лиану, мимо которой будет пролетать.
В данный момент Коко висит на первой лиане и хочет переместиться как можно дальше вправо.
Помогите Коко и определите максимальный номер лианы, до которой она сможет добраться.

Входные данные
Первая стока входных данных содержит целое число N (2 ≤ N ≤ 10⁵) — количество лиан.
Во второй строке записано целое число D (1 ≤ D ≤ 10⁹) — расстояние между соседними лианами.
В каждой из следующих N строк записано целое число ai (1 ≤ a_i ≤ 10⁹) — на сколько метров вправо может прыгнуть Коко, находясь на i-й лиане.

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

Примеры

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

Замечание
В примере из условия дано 5 лиан, а расстояние между лианами равно 3 метрам. Находясь на первой лиане, Коко может прыгнуть не более, чем на 7 метров, то есть она сможет допрыгнуть до второй и третьей лианы. Ей нужно остановиться на второй лиане, потому что со второй лианы длина прыжка равна 8 метрам, и это позволит ей допрыгнуть до четвёртой лианы. С четвёртой лианы длина прыжка равна 2 и это меньше, чем расстояние до следующей лианы, поэтому Коко остановится на четвёртой лиане.

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

Создайте структуру Point и сохраните исходные данные в массиве структур Point.

Входные данные
Программа получает на вход набор точек на плоскости. Сначала задано количество точек n, затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Величина n не превосходит 100, все исходные координаты – целые числа, не превосходящие 10³.

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

 Примеры

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

Билет на одну поездку в метро стоит 15 рублей, билет на 5 поездок стоит 70 рублей, билет на 10 поездок стоит 125 рублей, билет на 20 поездок стоит 230 рублей, билет на 60 поездок стоит 440 рублей. Пассажир планирует совершить n поездок. Определите, сколько билетов каждого вида он должен приобрести, чтобы суммарное количество оплаченных поездок было не меньше n, а общая стоимость приобретенных билетов – минимальна.

Входные данные
Дано одно число n - количество поездок.

Выходные данные
Выведите пять целых чисел, равные необходимому количеству билетов на 1, на 5, на 10, на 20, на 60 поездок. Если для какого-то данного n существует несколько способов приобретения билетов одинаковой стоимости, необходимо вывести ту комбинацию билетов, которая дает большее число поездок.

Примеры

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

Вам дана строка S, состоящая из цифр от 1 до 9 включительно. Вы можете вставить символ + в некоторые позиции (возможно, ни в одну) между двумя цифрами в этой строке. Здесь знак + не должен появляться последовательно после вставки (т.е. не должно быть два и больше знака + подряд). Все строки, которые можно получить таким образом, можно оценить как формулы. Оцените все возможные формулы и распечатайте сумму результатов, полученных при вычислении всех возможных формул.

Входные данные
На вход подается непустая строка S, состоящая из цифр от 1 до 9 включительно. Длина строки не более 10 символов.

Выходные данные
Выведите сумму результатов, полученных при вычислении всех возможных формул.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	125	176	Всего можно получить 4 формулы: 125, 1 + 25, 12 + 5 и 1 + 2 + 5. Результат после вычисления каждой формулы: 125 1 + 25 = 26 12 + 5 = 17 1 + 2 + 5 = 8 Таким образом, сумма 125 + 26 + 17 + 8 = 176.
2	9999999999	12656242944

 

Сегодня проходит памятный конкурс STCoder Contest 100. В этом случае Алиса хотела бы передать Громозеке целое число. Поскольку название конкурса - STCoder Contest 100, Громозека был бы счастлив, если бы ему дали положительное целое число, которое можно разделить на 100 ровно D раз. Найдите N-е наименьшее целое число, которое сделает Громозеку счастливым.

Входные данные
Во входной строке содержится два целых числа: D (равно 0, 1 или 2) и N (1<=N<=100).

Выходные данные
Выведите N-е наименьшее целое число, которое можно разделить на 100 ровно D раз.
 

 

Примеры

№	Входные данные	Выходные данные
1	0 5	5
2	1 11	1100
3	2 85	850000