Информатика

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

+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

На Новом проспекте построили подряд 10 зданий. Каждое здание может быть либо жилым домом, либо магазином, либо офисным зданием.

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

Входные данные
Программа получает на вход десять чисел, разделенных пробелами. Каждое число задает тип здания на Новом проспекте: число 1 обозначает жилой дом, число 2 обозначает магазин, число 0 обозначает офисное здание. Гарантируется, что на Новом проспекте есть хотя бы один жилой дом и хотя бы один магазин.

Выходные данные
Выведите одно целое число: наибольшее расстояние от дома до ближайшего к нему магазина. Расстояние между двумя соседними домами считается равным 1 (то есть если два дома стоят рядом, то между ними расстояние 1, если между двумя домами есть еще один дом, то расстояние между ними равно 2 и т.д.)

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 0 1 1 0 1 0 2 1 2	3	В примере из условия дальше всего идти до ближайшего магазина жителям четвертого дома: ближайший к их дому магазин находится в первом доме, и им нужно пройти три дома до него. Жителям других домов придется пройти меньшее расстояние до ближайшего магазина, поэтому ответ 3.

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	10 2 2 10	20 2 2 20 4 10 10 4
2	5 7 3 2	9 5 5 9

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

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

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

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

Входные данные
Вводится сначала K — вес предмета, который положили на левую чашу (1≤K≤50). Далее записано общее количество гирек N (1≤N≤10). Далее записано N различных натуральных чисел, не превышающих 50, — веса гирек.

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

Примеры

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

Все буквы латинского алфавита делятся на гласные и согласные. Гласными буквами являются: 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.

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

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

Планируется построить всего один завод в каком-нибудь городе, и развозить продукцию по остальным городам. Перевозка одной бочки в соседний город стоит один тугрик (местная валюта).

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

Входные данные
Первая строка входных данных содержит число N – количество городов ( N ≤ 10) и еще N чисел – количество кваса, требуемое ежедневно 1-м, 2-м, …, N -м городом (города нумеруются подряд вдоль кольцевой дороги).

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 5 3 10	3
2	6 4 4 1 5 1 3	2	На острове 6 городов, потребность каждого города указана в кружочках, номер города рядом с кружочком. Если построить завод во 2-м городе (он выделен серым), то потребуется заплатить 4 + 1 (стоимость перевозки в 1-й и 3-й города) + 5*2 + 3*2 (в 4-й и 6-й) + 1*3 (в 5-й см. рисунок). Во 2-й вообще ничего не везем. Это будет 24 тугрика. Легко проверить, что если построить завод в других городах, сумма будет больше. Например, если построить в 4-м городе, то сумма составит 1 + 1 + 3*2 + 4*2 + 4*3 = 28 тугриков.

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

Входные данные
Вводятся четыре числа, не превосходящие 100, задающие номера конечных остановок. Сначала для первого, потом второго автобуса (см. примеры и рисунок).

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 6 4 2	2	первый автобус ходит с 3-й остановки по 6-ю и обратно, а второй с 2-й по 4-ю и обратно. Пересесть с одного автобуса на другой можно на 3-й и 4-й остановках. Их две.
2	3 1 5 10	0	автобусы не имеют общих остановок.

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

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


Входные данные
В первой строке входных данных содержатся два числа: L - длина лавочки и K - количество гранитных блоков-ножек. Оба числа натуральные и не превышают 10 000.

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

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

Примеры

№	Входные данные	Выходные данные
1	5 2 0 2	2
2	13 4 1 4 8 11	4 8
3	14 6 1 6 8 11 12 13	6 8

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

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

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

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

Примеры

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

У Карлсона дома есть набор из n банок с конфетами. Банки пронумерованы от 1 до n , в i -й из них лежит a i конфет. Карлсон считает набор банок симпатичным , если в этом наборе нет трех банок с разным числом конфет.

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

Входные данные
Первая строка входных данных содержит натуральное число n ( 1 ≤ n ≤ 10⁵ ) — количество банок в наборе Карлсона.

Вторая строка входных данных содержит n целых чисел a_i ( 0 ≤ a_i ≤ 10⁹ ) — число конфет в банках. Соседние числа отделены друг от друга одним пробелом.

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

Примечание
В первом тесте из примера Карлсон может добавить в первую банку две конфеты, а во вторую банку — одну конфету. Тогда в первой и четвертой банках будет лежать по 7 конфет, а во второй и третьей — по 2 конфеты.

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

Примеры

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

В 2037-м году для создания научно исследовательской базы на Марс высадился отряд роботов, один из которых отправился собирать информацию о районе дислокации. В данный момент роботу из-за отказа некоторых узлов срочно необходимо вернуться в место закладки будущей базы.
Поверхность Марса в районе высадки десанта можно условно представить в виде плоскости с введенной на ней системой координат, такой, что база находится в точке (0, 0). Робот же остановился в точке (x₀, y₀). Он может перемещаться в четырёх направлениях:
• «R» — вправо, при этом координата x робота увеличивается на 1;
• «L» — влево, при этом координата x робота уменьшается на 1;
• «U» — вверх, при этом координата y робота увеличивается на 1;
• «D» — вниз, при этом координата y робота уменьшается на 1.
Из-за неисправности робот не может совершить два перемещения подряд в одном направлении.
Помогите роботу вернуться на базу. Робот должен сделать не более 10000 передвижений, иначе он разрядится и не доедет до базы!

Входные данные
В единственной строке входных данных находятся два целых числа x0 и y0 — изначальные координаты робота (−1000 ≤ x0, y0 ≤ 1000).

Выходные данные
В первой строке выведите целое число, не большее 10000 — количество операций, которые должен сделать робот. Во второй строке выведите сами операции. Каждая операция задаётся одной буквой:
вправо — «R» влево — «L», вверх — «U», вниз — «D». Символы необходимо выводить без пробелов между ними.
 

Примеры

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

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

Скоро у Гарри Поттера день рождения! Гермиона хочет приготовить для него необычный подарок. Она хочет подарить Гарри набор из n волшебных конфет. Каждая конфета характеризуется её вкусом — целым числом t_i . Удовольствие , которое получит Гарри от набора конфет — это сумма вкусов всех конфет в этом наборе. Обратите внимание, что вкусы конфет, как и удовольствие Гарри, не обязательно должны быть положительными.

У Гермионы есть огромная коробка с конфетами, в которой для каждого целого числа t от - 10⁹ до 10⁹ лежит ровно одна конфета со вкусом t . Гермиона хочет взять из этой коробки n конфет, из которых будет состоять набор для Гарри.

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

Входные данные
Первая строка входных данных содержит единственное целое число n ( 1 ≤ n ≤ 100 ) — количество конфет, которое хочет Гермиона положить в набор. Вторая строка входных данных содержит единственное целое число s ( - 10⁹ ≤ s ≤ 10⁹ ) — удовольствие, которое должен получить Гарри от набора.

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

Примеры

№	Входные данные	Выходные данные
1	3 10	YES 500000000 -500000000 10

Давным-давно большинство персональных компьютеров были оборудованы видеокартами, работавшими только в текстовом режиме. Если программист хотел изобразить картинку на экране, ему приходилось использовать псевдографику или ASCII-графику. Вот пример картинки, нарисованный с ее помощью:

^..^
(OO)
/  \
()()

Вам дан многоугольник, нарисованный с помощью ASCII-графики. Ваша задача состоит в том, чтобы посчитать количество его сторон.
Картинка состоит из символов ‘.’, ‘\’ и ‘/’. Каждый символ изображает единичный квадрат картинки. Символ ‘.’ обозначает пустой квадрат, символ ‘/’ — квадрат с отрезком из левого нижнего угла в правый верхний, а символ ‘\’ — квадрат с отрезком из левого верхнего угла в правый нижний.


Входные данные
Первая строка входных данных содержит два числа h и w — высота и ширина изображения (2 ? h, w ? 100). Следующие h строк, по w символов в каждой, содержат описание многоугольника, нарисованного с помощью ASCII-графики.
Гарантируется, что картинка содержит ровно один многоугольник, не имеющий самопересечений и самокасаний.

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

Примеры

№	Входные данные	Выходные данные
1	4 4 /\/\ \../ .\.\ ..\/	8

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

Сегодня у Вити день рождения, и он показал свои записи Алёне. Витя знает, что она тоже любит исследовать всякие наборы чисел и находить в них закономерности. Алёна тут же заметила интересный момент: когда в один из прошлых дней рождения Вите было 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 градусов или ниже, а в демисезонной – при температуре выше x градусов. В общем, жить бы ему и радоваться. Но откуда бы тогда появиться задаче?

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

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

Входные данные
В первой строчке даны два вещественных числа x и d — граница температуры между куртками и отклонение температуры, которое герой задачи считает незначительным (−89≤x≤55, 1≤d≤6 ).

Во второй строчке дано целое число n, 1≤n≤10⁵ — количество дней в архиве прогноза погоды.

В третьей строчке перечислены n вещественных чисел ti — температура в i-й день (−89≤t_i≤55 ).

Выходные данные
Выведите одно число: количество дней, в которые герою задачи было некомфортно в той куртке, в которой он вышел в этот день
 

Примеры

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

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

Улицы в новой столице образуют правильную прямоугольную сетку, в которой все улицы пересекаются ровно через одну местную единицу длины. Вертикально идущие улицы называются улицами, а горизонтально идущие — аллеями. Всего в городе получилось 2000 улиц и 2000 аллей, поэтому, чтобы не придумывать много новых названий, их все просто пронумеровали. Улицы пронумеровали с запада на восток числами от −1000 до 999, а аллеи — с юга на север, тоже числами от −1000 до 999. Центром города считаются кварталы на пересечении улиц и аллей с номерами от −100 до 100.

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

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

Входные данные
В первой строке даны два числа x1 и y1 — номер улицы и номер аллеи, на пересечении которых находится мэрия. В второй строке даны два числа x2 и y2 — номер улицы и номер аллеи, на пересечении которых находится дом мэра. Все числа целые и не превосходят по модулю 100.

Выходные данные
Выведите одно число: длину кратчайшего пути от мэрии до дома мэра на автомобиле.-
 

Примеры

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

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

Воспитательница работает в детском саду уже много лет, и отлично разбирается в детском настроении. Ей достаточно посмотреть на ребенка, чтобы понять, насколько он сегодня плаксив: заплачет ли он сегодня сам из-за того, что компот невкусный, разрыдается ли из-за того, что Катя и Ваня уже плачут, а он еще нет, или же будет сосредоточенно играть c кубиками, не обращая внимание на слезы и сопли товарищей.

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

Входные данные
В первой строке дано целое число n (1n1000) — количество детей в группе. В следующей строке через пробел перечислены n чисел, причем i-е по счету число qi (0qin−1  ) обозначает плаксивость i-го ребенка. Число qi обозначает количество детей, которые должны заплакать, чтобы этот ребенок тоже заплакал. Если qi = 0, значит, этот ребенок точно сегодня заплачет просто так, вне зависимости от своих товарищей. Считается, что ребенок не может начать плакать, если вокруг него не плачет нужное количество детей. Если ребенок начал плакать, то он уже не успокоится до вечера.

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

Примеры

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