Типы данных

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

По дороге одна за другой движутся 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.

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	aaaza aazzaa azzza	aazza
2	xy xxyy yx	IMPOSSIBLE

Телефонные номера в адресной книге мобильного телефона имеют один из следующих форматов:

+7<код><номер>

8<код><номер>

<номер>

где <номер> — это семь цифр, а <код> — это три цифры или три цифры в круглых скобках. Если код не указан, то считается, что он равен 495. Кроме того, в записи телефонного номера может стоять знак “-” между любыми двумя цифрами (см. пример).

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

Два телефонных номера совпадают, если у них равны коды и равны номера. Например, +7(916)0123456 и 89160123456 — это один и тот же номер.

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

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

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

Примеры

№	Входные данные	Выходные данные
1	8(495)430-23-97 +7-4-9-5-43-023-97 4-3-0-2-3-9-7 8-495-430	YES YES NO

Миша готовится к ЕГЭ по информатике. Сейчас он изучает задачу A4, в которой описывается работа с масками файлов:

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

Символ «?» (вопросительный знак) означает ровно один произвольный символ.

Символ «*» (звёздочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность.

Поскольку открытого банка задач для ЕГЭ по информатике не существует, Мише приходится тренироваться самостоятельно. Напишите программу, которая для каждого имени файла определит, подходит ли оно под заданную маску, чтобы Миша мог сверить свои ответы. Гарантируется, что в маске файла присутствует не более одного символа «*».

Входные данные
В первой строке содержится маска файла. В следующих 5 строках содержатся имена файлов по одному в строке. Имена файлов состоят из маленьких латинских букв, цифр и символа «.» (точка), в маске также могут содержаться символы «?» и «*» (символ «*» — не более одного раза). Длина каждой строки не превосходит 20 символов.

Выходные данные
Для каждого имени файла выведите слово «YES» если оно удовлетворяет маске и «NO» иначе. Выводить слова следует большими латинскими буквами без кавычек, каждое в новой строке.

Примеры

№	Входные данные	Выходные данные
1	?or*.d?? fort.doc ford.doc lord2.doc orsk.dat port	YES YES YES NO NO

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

По данным числам N, M и K определите наименьшее количество рулонов, которое нужно купить Пете, чтобы оклеить всю стену.

Формат входных данных
Вводятся натуральные числа N, M и K (1 ≤ N ≤ 100, 1 ≤ M ≤ 100, N ≤K ≤100).

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

«Нарисуйте» с помощью символов на экране лес. При этом не пользуйтесь командами перемещения курсора по экрану. Ваша программа должна последовательно выводить символы строк (или строки целиком).

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

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

Елочки должны изображаться символами «#» (решеточка), а пустые места между ними — символами «.» (точка). Во всех строках должно быть выведено одинаковое количество символов, при этом обязательно должна быть строка, в которой последним символом является решеточка, в последней строке обязательно должны быть решеточки (т.е. должен быть выведен прямоугольник из точек и решеточек, в нем не должно быть лишних столбцов и строк).

Входные данные
Вводится число елочек N, а дальше N пар натуральных чисел, описывающих елочки: первое число каждой пары задает количество треугольников в елочке, а второе — размер самого маленького треугольника. Елочки описываются в порядке слева направо (если смотреть на вершины елочек).

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

Выходные данные
Выведите требуемый «рисунок». Для лучшего понимания смотрите примеры.
 

Примеры

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

В школе продолжительность каждого урока 45 минут, а перемены между уроками – всего 5 минут. Первый урок начинается ровно в 8 часов утра. Напишите программу, отвечающую на вопрос «во сколько в этой школе заканчивается K-ый урок?»

Формат входных данных
Вводится одно натуральное число K, не превышающее 15.

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

Все буквы латинского алфавита делятся на гласные и согласные. Гласными буквами являются: a, e, i, o, u, y. Остальные буквы являются согласными.

Слово называется благозвучным, если в этом слове не встречается больше двух согласных букв подряд и не встречается больше двух гласных букв подряд. Например, слова abba, mama, program — благозвучные, а слова aaa, school, search — неблагозвучные.

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

Входные данные
Вводится слово, состоящее только из маленьких латинских букв. Длина слова не превышает 30 символов.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	program	0	Слово уже является благозвучным.
2	school	1	Достаточно добавить одну гласную букву, например, между буквами s  и с

Витя подключен к интернет по следующему тарифному плану. Ежемесячная абонентская плата составляет A рублей, и в эту абонентскую плату включено B мегабайт трафика. Неизрасходованные мегабайты в конце месяца «сгорают». Если трафик превышает B мегабайт, то каждый мегабайт трафика сверх предоплаченных стоит C рублей.

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

Формат входных данных
Вводятся четыре натуральных числа A, B, C, D. Все числа не превышают 100.

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

Секретное агентство «Super-Secret-no» решило для шифрования переписки своих сотрудников использовать «метод бутерброда». Сначала буквы слова нумеруются в таком порядке: первая буква получает номер 1, последняя буква - номер 2, вторая – номер 3, предпоследняя – номер 4, потом третья … и так для всех букв (см. рисунок). Затем все буквы записываются в шифр в порядке своих номеров. В конец зашифрованного слова добавляется знак «диез» (#), который  нельзя использовать в сообщениях.

Например, слово «sandwich» зашифруется в «shacnidw#».



К сожалению, программист «Super-Secret-no», написал только программу шифрования и уволился. И теперь агенты не могут понять, что же они написали друг другу. Помогите им.

Входные данные
Вводится слово, зашифрованное методом бутерброда. Длина слова не превышает 20 букв.

Выходные данные
Выведите расшифрованное слово.

Примеры

№	Входные данные	Выходные данные
1	Aabrrbaacda#	Abracadabra

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

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

Входные данные
На вход программы поступают 3 натуральных числа, записанных через пробел - N, M и K, каждое из них не превосходит 10 000.

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

Примеры

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

Марина очень любит палиндромы. Палиндром — это строка, которая одинаково читается слева направо и справа налево, например « noon », « rotator » или « radar ».

Марина написала на доске строку s , состоящую из n строчных латинских букв s₁ s₂ ... s_n . Подстрокой строки s называется строка s _{ls l + 1} ... s_r для некоторых 1 ≤ l ≤ r ≤ n . Марина ищет в строке s как можно более длинную подстроку, которая является палиндромом. Например, в строке « rotateradars » такой подстрокой будет « radar ».

Вова хочет изменить написанную Мариной строку, чтобы подстрока-палиндром была как можно длиннее. Он может либо оставить строку нетронутой, либо изменить в ней ровно одну букву на другую. Например, если в строке « rotateradars » изменить шестую букву на « o », получится строка « rotatoradars », в которой максимальная подстрока-палиндром « rotator » имеет длину 7 . Подстроку-палиндром большей длины получить нельзя.

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

Входные данные
Первая строка входных данных содержит натуральное число n — длину строки, которую написала Марина ( 1 ≤ n ≤ 100 ).

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

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

Примеры

№	Входные данные	Выходные данные
1	12 rotateradars	7

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

Сегодня у Вити день рождения, и он показал свои записи Алёне. Витя знает, что она тоже любит исследовать всякие наборы чисел и находить в них закономерности. Алёна тут же заметила интересный момент: когда в один из прошлых дней рождения Вите было n лет, его брату было m лет, а сегодня Витя младше своего брата ровно в k раз!

Вернувшись вечером домой, Алёна заинтересовалась вопросом: а достаточно ли этих данных, чтобы вычислить, сколько лет исполнилось Вите сегодня? Алёна быстро справилась, а сможете ли вы решить эту сложную задачу и выяснить по числам n , m и k , сколько лет Вите?

Входные данные
Ввод состоит из трех строк, которые содержат по одному натуральному числу: n , m и k — возраст Вити и его брата в былые времена, а также во сколько раз Витя сегодня младше своего брата ( 1 ≤ n < m ≤ 10 000 , 2 ≤ k ≤ 10 000 ).

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

Если Витя и Алёна ошиблись, и описанной ситуации быть не могло, выведите число - 1 .
 

№	Входные данные	Выходные данные
1	4 15 2	11
2	4 15 3	-1
3	4 8 2	-1

А мы, тем временем, возвращаемся в поезд Москва-Адлер, где Максим все-таки был пойман папой, и три рулона туалетной бумаги не были выпущены из окна первого вагона («Ну паааап, ну мне было интересно, что длиннее — поезд или бумага, ну не надо за ухо»).

Теперь Максим сидит в купе вместе с мамой. Чтобы отвлечь его от продумывания деталей новых экспериментов, мама — неплохой математик — рассказала Максиму одну любопытную задачу («Мои студенты в среду ее так и не смогли решить, совсем считать разучились»).

Дано число x. Каждую его цифру нужно умножить на 19, прибавить к результату 40, полученное число снова умножить на 19, взять последнюю цифру этого произведения и поставить его на место исходной цифры в числе x. Вопрос: какое число получится в итоге?

Максим, впрочем, решил задачу гораздо быстрее, чем ожидала его мама, и, к сожалению, снова был готов к экспериментам. А сможете ли вы?

Входные данные
Дано целое число x (0≤x≤10000).

Выходные данные
Выведите одно число: ответ на задачу, которую мама рассказала Максиму.

Примеры

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

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

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

Ваша задача — помочь правительству этой страны защитить детей от вредной информации. Напишите программу, которая будет проверять, нет ли в данной строке запрещенного слова, учитывая возможное коварство сайтовладельцев. Известно, что сайтовладельцы иногда делают следующие замены: e  3, o  0, i  1, t  7, a  4, s  5.

Входные данные
В первой строке входных данных дана строка — текст с сайта. Во второй строке входных данных дана другая строка — запрещенное слово. Первая строка состоит из маленьких латинских букв и цифр, вторая строка состоит только из маленьких латинских букв. Длина каждой строки не превышает 100.

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

Примеры

№	Входные данные	Выходные данные
1	inah0leinthegroundthereliv3dah0bb1t hobbit	YES
2	whath4v3igotinmypocket handses	NO
3	whath4veig0t1nmyp0ck37 knife	NO
4	wh4thav31go71nmyp0ck3t stringofnothing	NO

Когда Дядя Фёдор уехал домой в город, следить за хозяйством остались Матроскин и Шарик. Но поскольку Дядю Фёдора очень волновали дела в Простоквашино, они договорились, что каждую неделю Матроскин будет писать письмо с отчетом о делах. Довольно скоро Матроскин понял, что письма идут слишком долго, поэтому решил отправлять телеграммы. Обычно отчеты очень длинные, поэтому Матроскину пришлось отправлять несколько телеграмм. Чтобы Дяде Фёдору было удобнее разобраться в пришедших телеграммах, Матроскин следует следущим правилам:

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

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

Входные данные
На вход подается строка из маленьких латинских букв и пробелов. Она не начинается и не заканчивается пробелами и никакие два пробела в ней не идут подряд. Длина строки не превышает 10000.

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

 

Примеры

№	Входные данные	Выходные данные
1	deesecnj vmguhee xhled rrr dfjhj fdytiaf baulvovt kvhygzhv wfaocftf scugmcqsk wadi bjeiq coesxqgnry tmlko gpmwns rcf dtdey bvirmlv gzl bwuoio	2 deesecnj vmguhee xhled rrr dfjhj fdytiaf baulvovt kvhygzhv wfaocftf scugmcqsk wadi bjeiq coesxqgnry tmlko gpmwns rcf dtdey bvirmlv gzl... ...bwuoio

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

Вот и сейчас стоило Максиму выйти из здания вокзала, как начался ливень. Зонтик, согласно всем законам подлости, лежит у него на дне чемодана, и лезть за ним совсем не хочется. Да и вот же — совсем рядом есть автобусная остановка, под которой можно укрыться от дождя. Нужно всего лишь перейти улицу, и все! «Не бывает все так просто», — пришло в голову Максиму. И действительно — не бывает.

Дело в том, что на улице, которая отделяет Максима от остановки, меняют асфальт. Старый слой асфальта уже сняли (там теперь ямы, поэтому пройти там невозможно), и теперь по улице, приближаясь к Максиму, со скоростью v2 м/мин мужественно ползет асфальтоукладчик, оставляя за собой новый, аккуратно уложенный асфальт. Правда, прежде, чем по новому асфальту можно будет ходить, он должен остывать T минут. Асфальтоукладчик только что начал работу, поэтому весь асфальт за ним был залит еще вчера и уже успел остыть.

Конечно же, Максим не хочет мокнуть, поэтому он пытается оказаться на другой стороне улицы как можно быстрее. Он бегает со скоростью v1 м/мин. Известна ему и ширина улицы — L м. Максим может ходить вдоль улицы по тротуару сколько ему хочется. Находиться на проезжей части он хочет как можно меньше, поэтому переходит улицу он только перпендикулярно.

Входные данные
Даны целые числа L, D, T, v1, v2 — ширина улицы, расстояние до асфальтоукладчика, время, которое остывает асфальт (в минутах), скорость Максима и скорость асфальтоукладчика. (1 ≤ L ≤ 100, 1 ≤ D ≤ 100, 1 ≤ T ≤ 100, 1 ≤ v1 ≤ 100, 1 ≤ v2 ≤ 100).

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

Примеры

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

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

Однажды друзья познакомили Артура с девушкой по имени Нина (о, какое прекрасное имя!). Она была очаровательна и очень болтлива, поэтому Артуру почти не нужно было подбирать слова — она заполняла неловкую тишину за него. Разумеется, он пригласил ее в кафе выпить чашечку кофе. Артур даже продумал все свои реплики заранее: «Счастлив тебя видеть», «Ты сегодня восхитительна», «Да, конечно, я внимательно тебя слушаю», «И что дальше?», «Счет, пожалуйста» и, конечно, «Я позвоню тебе на днях, не скучай».

Но, как известно, не бывает идеальных планов. Все шло как по маслу, но вдруг, сидя за столиком в кафе, Нина сказала, что ужасно не выспалась и не отказалась бы от N чашек кофе. И тут Артур понял, что он не обдумал заранее, как он будет делать заказ. Понятно, что нужно сказать что-то вроде: «Сколько-то чашек кофе, пожалуйста», но вот сколько же чашек нужно, чтобы Нина так и не поняла, что Артур не выговаривает букву «р»? Явно нужно заказать не меньше, чем N + 1 чашку — чтобы и Нине досталось N чашек, и самому выпить, но вот сколько точно — Артур не знает. Денег у него не слишком много, поэтому заказывать больше, чем жизненно необходимо для того, чтобы избежать разоблачения, Артур не хочет.

Помогите Артуру — посчитайте, сколько чашек кофе он должен заказать.

Входные данные
Вводится одно целое число N (1 ≤ N ≤ 2999).

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

Примеры

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

Алиса и Боб — очень опытные шпионы. Лучше всего им удается находить пароли для доступа к различным секретным данным. Вот и в этот раз Алиса получила от Боба сообщение, в котором говорилось, что ключом является число и далее шло само это число. Также Боб писал, что число-ключ должно делиться на 9. Когда Алиса попробовала ввести полученный пароль, то оказалось, что он не подходит. Алиса очень доверяет Бобу, и поэтому она решила, что Боб мог ошибиться только в одной цифре пароля. Поскольку у Алисы не так много времени, она решила не выяснять у Боба правильный ответ, а перебрать все числа, которые могли бы быть паролем, т.е. все такие числа, которые могут быть получены из того числа, которое прислал Боб, заменой ровно одной из его цифр и делятся на 9. За помощью Алиса обратилась к вам. Напишите программу, которая предложит Алисе все возможные варианты пароля.

Входные данные
Во входных данных содержится единственное число P (1 ≤ P ≤ 10⁹) — то число, которая Алиса получила в сообщении от Боба. Гарантируется, что оно не начинается с нуля.

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

Примеры

№	Входные данные	Выходные данные
1	256	756 216 252