задачи с dataart

Problem A-Таинственная программа

Задача A

Time limit:	1 s
Memory limit:	128 M

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

Каково же назначение этой программы, рассказывать расстроенный зверёк отказался, но буркнул, что надо для каждого числа от 0 до M подсчитать число раз, которое число встречается в N-элементном массиве. Если бы требовалось решить задачу для N = 3, M = 1, восстановленный код выглядел бы так:

if (arr[0]==0) ++count[0];
if (arr[0]==1) ++count[1];
if (arr[1]==0) ++count[0];
if (arr[1]==1) ++count[1];
if (arr[2]==0) ++count[0];
if (arr[2]==1) ++count[1];

К несчастью, чисел больше, а массив объёмнее. Зато код пишется быстро: одна строчка за одну секунду. Зная это, помогите для заданных N и M оценить время восстановления программы.

Исходные данные
Единственная строка содержит целые числа N (0 <= N <= 40000) и M (0 <= M <= 40000).

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

Examples

Input	Output
3 1	6

Problem B-Вредитель

Задача B

Time limit:	1 s
Memory limit:	64 M

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

После лёгкой воспитательной работы, Баги рассказал, что входную последовательность преобразует следующим образом: подряд идущие одинаковые числа заменяются на пару "количество чисел - само число" (если число одно, то количество равно 1). Проги потребовалось несколько часов, чтобы понять логику вредителя. У вас же этого времени нет, но с помощью примера вам нужно повторить преобразующий алгоритм.

Исходные данные
В первой строке находится целое число N — количество чисел во входном наборе (1 <= N <= 1000). Во второй строке через пробел записаны эти числа. Все числа натуральные и не превосходят 10.

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

Examples

Input	Output
5 2 4 4 4 5	1 2 3 4 1 5

---

Problem C-Странная орфография

Задача C

Time limit:	1 s
Memory limit:	64 M

Будем честны: каждый ДатаАрт забывал названия дней недели, отметить нужное время в системе и исключить из списка адресатов большие рассылки. Для профилактики подобных вещей Главный ДатаАрт посоветовал порешать простые задачи.

Одной из таких задач является расшифровка текста, закодированного по следующему принципу: сначала выбирается средний символ текста (если нумеровать символы в тексте от 1 до n, то средний символ имеет номер (1 + n) div 2), затем по этому же правилу выписывается сначала левый кусок текста, а потом правый. Например, если изменить по этому правилу слово "орфография", то получится "грофофраия".

Исходные данные
В единственной строке приведён закодированный текст. Текст содержит не более 20000 символов: букв латинского алфавита, пробелов и знаков препинания.

Результат
Выведите единственную строку, содержащую "расшифрованный" текст.

Examples

Input	Output
orthography	gtorhoprahy

---

Problem D-Дороги

Задача D

Time limit:	1 s
Memory limit:	64 M

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

Исходные данные
В первой строке задано число N (2 <= N <= 100) - количество городов с ДатаАртами.
В каждой из следующих N строк приведены N чисел: если на i-той строке в j-том столбце стоит 0 - между i-тым и j-тым городами нет дороги; если стоит 1 - есть дорога.
Значения на i-той строке в j-том столбце и на j-той строке в i-том столбце совпадают (дороги двусторонние).
Гарантируется, что для любой пары городов существует маршрут проезда.

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

Examples

Input	Output
3 0 1 1 1 0 1 1 1 0	No

---

Problem E-Непростая задача

Задача E

Time limit:	1 s
Memory limit:	64 M

В перерывах между программированием Проги любит скоротать время за чтением книги. Вот, например, одна из них: "Далеко-далеко, в не замеченных картографами складках давно вышедшего из моды Западного Спирального Рукава Галактики, затерялась крохотная, никому не интересная желтая звезда. Вокруг нее, на расстоянии примерно девяноста восьми миллионов миль, обращается ничтожная зелено-голубая планетка, обитатели которой все еще очень похожи на своих предков-обезьян – достаточно сказать, что электронные часы до сих пор считаются у них чудом техники. У этой планеты есть – вернее, была – одна проблема: большинство живущих на ней людей только и делали, что страдали, так как не находили в жизни счастья. Рождалось множество решений, но почти все они сводились к перераспределению маленьких зеленых клочков бумаги – что само по себе весьма странно, так как кто-кто, а маленькие зеленые клочки бумаги никаких страданий не испытывали, ибо счастья не искали. Решение все никак не находилось, и планета полнилась озлобленными людьми, для большинства из которых ощущение несчастья было постоянным, и даже электронные часы не скрашивали им жизнь. Постепенно распространялось и крепло убеждение, что все несчастья пошли с того, как люди спустились с деревьев на землю. А кое-кто даже полагал, что ошибка была совершена еще раньше – с деревьями тоже нечего было связываться и вообще незачем было вылезать из океана. И вот как-то в четверг, после дождя, спустя почти две тысячи лет после того, как одного человека приколотили гвоздями к дереву за то, что он призывал хотя бы иногда, просто для разнообразия, относиться друг к другу по-хорошему, некая девушка, сидя в одиночестве за столиком маленького кафе в Рикмансворте, вдруг додумалась, в чем была вся загвоздка и каким образом мир все-таки можно сделать обителью счастья и покоя. На сей раз дело в шляпе, все непременно получится – и никаких гвоздей и приколачиваний живых людей к деревьям и прочим предметам! К сожалению, не успела она дойти до телефона, чтобы поделиться с кем-нибудь своим открытием, произошла чудовищно нелепая катастрофа, и решение было навсегда потеряно. Впрочем, история, которую я собираюсь вам поведать, не о девушке. Это история о чудовищно нелепой катастрофе и некоторых ее последствиях. Также это история о книге. О книге под названием "Автостопом по Галактике: Путеводитель вольного странника", в обиходе именуемой просто "Путеводитель" – книге, написанной не на Земле, никогда на Земле не публиковавшейся и до катастрофы неизвестной ни одному землянину. Тем не менее это замечательная книга. Пожалуй, это самое замечательное из всех изданий грандиозной Издательской корпорации Малой Медведицы – также неизвестной ни одному землянину. Книга пользуется огромным спросом, оставив далеко позади "Межзвездный сборник советов по домоводству"; раскупается гораздо быстрее, чем "Еще 53 способа скоротать время в невесомости", и вызывает еще больше споров и толков, чем философская трилогия "Где Господь сбился с пути", "Основные ошибки Господа Бога" и "Да кто он в конце концов такой, этот Господь Бог?!" В просвещенных и расслабленных цивилизациях Внешнего Восточного Кольца Галактики "Путеводитель" вытеснил даже великую "Большую Галактическую Энциклопедию" в качестве общепризнанного кладезя мудрости и знаний. Ибо, несмотря на обилие пропусков и вопиюще искаженной, а то и просто-напросто апокрифической информации, "Путеводитель" обладает двумя важнейшими преимуществами перед "Энциклопедией". Во-первых, он дешевле. Во-вторых, на титульном листе крупными буквами выведены сакраментальные слова: "НЕ ПАНИКУЙ". Но история о том чудовищно нелепом четверге, его удивительных последствиях и о роли, которую сыграла во всем этом вышеназванная замечательная книга, – так вот, эта история начинается довольно банально. Она начинается с дома." Тут заканчивается вступление. Вы, конечно, можете продолжить читать это увлекательное повествование, но задание требует, чтобы вы вывели на экран число сорок два. В любом случае, первая глава начинается так: "Дом стоял на небольшой возвышенности на самом краю поселка. Он был ничем не примечателен – построенный лет тридцать назад, кирпичный, маленький, невзрачный, с четырьмя окнами на фасаде. Словом, один из тех, от которых тут же хочется отвести взгляд. Единственным человеком, полюбившим это чахлое строение, был Артур Дент, да и то лишь потому, что жил в нем. Жил уже три года, с тех пор как уехал из Лондона – Лондон был вреден для его нервной системы. От роду Артуру было столько же, сколько и дому, – около тридцати. Высокий, темноволосый, он вечно был не в ладах с самим собой. Заботило его больше всего то, что люди постоянно приставали к нему с расспросами, почему это у него такой озабоченный вид. Он работал на местной радиостанции, что, как твердил Артур своим знакомым, гораздо интереснее, чем все думают. И был совершенно прав – большинство его знакомых работали в рекламе. В среду ночью лил дождь, лужайка раскисла и потекла, но на следующее утро облака разошлись, и солнце ярко осветило дом Артура Дента – как выяснилось, в последний раз. Артуру все еще было невдомек, что муниципалитет принял решение снести его дом и проложить на этом месте скоростное шоссе. В четверг в восемь часов утра Артур чувствовал себя далеко не блестяще. Он едва разлепил веки, с трудом обошел комнату, открыл окно, увидел бульдозер, нашел тапочки и поплелся в ванную. Склонившись над раковиной, Артур машинально почистил зубы. Выпрямился. Зеркало для бритья отражало потолок. Поправил зеркало – и на секунду, через окно в ванной, оно отразило второй бульдозер. Установленное правильно, оно отразило щетину на лице Артура Дента. Артур побрился, плеснул в лицо водой, вытерся и зашлепал на кухню. Чайник, розетка, холодильник, молоко, кофе. Зевок. На какой-то миг в поисках ассоциативных связей в голове всплыло слово "бульдозер". Бульдозер за окном кухни казался громадным. Артур тупо уставился на него. "Желтый", – подумал он и побрел в спальню одеваться. Проходя мимо ванной, он остановился и выпил стакан воды, потом еще один. "Похмелье? – мелькнула мысль. – Откуда похмелье?" Он что, пил вчера вечером? Вероятно, пил, пришел к выводу Артур и тут заметил в зеркале какое-то движение. "Желтое", – подумал он и вернулся в спальню. Пивная. О Боже, пивная! Артур смутно припомнил злость, которую испытывал по поводу… чего? Факт тот, что это "что-то" его весьма раздражало. Он рассказывал об этом окружающим, долго и пространно, и самым отчетливым воспоминанием были остекленелые лица слушателей. Что-то там о новом шоссе… Артур взглянул на себя в зеркало шкафа и высунул язык. "Желтый", – подумал он. Слово "желтый" всплыло в поисках ассоциативных связей. Пятнадцатью секундами позже он оказался на дворе и плюхнулся на землю перед большим желтым бульдозером, который надвигался на его сад. Мистер Л. Проссер был, как принято говорить, всего лишь человеком, иными словами, основанной на углероде двуногой формой жизни, ведущей свое начало от обезьяны. Выражаясь конкретнее, это был сорокалетний, преждевременно располневший, неоднократно битый жизнью муниципальный служащий. Любопытный факт, неизвестный мистеру Проссеру: он являлся прямым потомком Чингисхана, хотя промежуточные поколения так исказили гены, что в нем не сохранилось никаких монголоидных черт. От могущественного предка осталась лишь склонность к маленьким меховым шапочкам. Мистер Проссер никоим образом не был великим воином; напротив, то был очень нервный, вечно чем-то озабоченный человек. Сегодня он нервничал и хлопотал как никогда, потому что работа совсем не клеилась. А заключалась его работа в том, чтобы до конца дня убрать с дороги дом Артура Дента..."

Исходные данные
В единственной строчке заданы три целых неотрицательных числа, каждое из которых не превышает 10000.

Результат
Выведите единственное требуемое число.

Examples

Input	Output
1 0 41	42

---

Problem F-Отрезки

Задача A

Time limit:	1 s
Memory limit:	64 M

Когда сталкиваются титаны - меняется мироздание. Когда Баги хочет укусить Проги - вы получаете новую задачу.

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

Исходные данные
В единственной строке заданы 8 целых чисел - координаты (x, y) точек A, B, C, D.Каждая пара чисел разделена одним пробелом. Каждое из чисел не превышает по абсолютной величине 1000.

Результат
Выведите единственное число - общую часть проекций. Если общей части нет, вывести -1, если это одна точка - вывести 0.

Examples

Input	Output
2 2 7 5 3 4 8 1	4

---

Problem G-2^a*3^b*5^c

Задача G

Time limit:	1 s
Memory limit:	64 M

Сколько натуральных чисел вида 2^a*3^b*5^c (a,b,c - неотрицательные целые числа) принадлежат отрезку [M;N]?

Исходные данные
Вы вводите с клавиатуры 2 целых числа - M и N. Каждое из чисел не превышает по абсолютной величине 10000.

Результат
Вы выводите на экран одно число - искомое количество чисел.

Examples

Input	Output
10 20	6

---

Problem H-ЗООФЕРМА

Задача H. ЗООФЕРМА.

Time limit:	1 s
Memory limit:	64 M

Исследования учёных показали, что количество коз (G), коров (C) и свиней (P) на зооферме с течением времени приближённо изменяется в соответствии с законом

G^N+C^N=P^N,

где N – количество лет (N>=2).

В общем случае получается дробное количество коз, коров и свиней. Однако, для некоторых N можно указать и целые значения. Например, для N=2 получим: G=3, C=4, P=5.

Составьте программу, которая для заданного N>=3 находит такие целые положительные G, C, P, которые удовлетворяют закону.

---

Problem I-Положительный минимум

Задача I

Time limit:	1 s
Memory limit:	64 M

Дана последовательность N целых чисел. Найти наименьший положительный элемент этой последовательности.

Вы вводите с клавиатуры количество чисел N и N целых чисел - элементов этой последовательности не превышает 10000, каждый элемент последовательности не превышает по абсолютной величине 1000.

Результат
Вывести на экран искомый элемент. Если в последовательности нет положительных элементов - вывести 0.

Examples

Input	Output
7 -4 4 -7 3 0 8 2	2

---

Problem J-Цифры

Задача J

Time limit:	1 s
Memory limit:	64 M

Задано натуральное число N. Найти наименьшее и наибольшее число, состоящее из тех же цифр и в таком же количестве, что и N.

Исходные данные
Вы вводите с клавиатуры число N (1 <= N <= 2000000000).

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

Examples

Input	Output
7051	1057 7510

---

Problem K-3*N+1

Задача K. 3*N+1

Time limit:	1 s
Memory limit:	64 M

Для заданного целого N (N>=1) построим последовательность по такому правилу:

1. 1-е число — это N;

2. если предыдущее число — чётное, то следующее число — в два раза меньше;

3. если предыдущее число — нечётное, то следующее число равно 1 плюс число в три раза большее, чем предыдущее.

Пример последовательности при N=3:

3 7 22 11 34 17 52 . . .

Найти наименьшее N (N>=1), при котором последовательность не содержит число 1.

---

Problem L-Не цифры

Задача L

Time limit:	1 s
Memory limit:	64 M

Задана текстовая строка, состоящая из ASCII-символов. Изъять из нее все символы, не являющиеся цифрами. Считать, что строка содержит хотя бы одну цифру.

Исходные данные
Вы вводите с клавиатуры строку, длина которой не превышает 255 символов.

Результат
Вы выводите на экран искомую строку.

Examples

Input	Output
Ф11р88н	1188

---

Problem M-Одного цвета

Задача M

Time limit:	1 s
Memory limit:	64 M

Дано K клеток шахматной доски. Выяснить, все ли они одного цвета.

Исходные данные
Вы вводите с клавиатуры N - количество контрольных примеров (1 <= N <= 100), потом число К - количество клеток шахматной доски (1 <= K <= 100), а в следующих К строках - координаты клеток (натуральные числа, не большие 8).

Результат
Вы выводите на экран для каждого примера 1, если все клетки одного цвета, и 0, если это не так.

Examples

Input	Output
3 3 1 2 8 1 8 5 2 1 1 1 2 2 1 1 2 2	101