Информатика

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

Внутри такой счетчик устроен следующим образом: в нем есть три диска с надписанными на ребре цифрами от 0 до 9. Диски надеты на ось, к которой подсоединена кнопка. Изначально на каждом из трёх дисков записана цифра 0. При нажатии на кнопку один или несколько дисков проворачиваются так, чтобы записанное в данный момент на счетчике число увеличилось на 1. Каждый диск при нажатии на кнопку проворачивается только на одно число вперед. Если за одно нажатие проворачивается несколько дисков, сначала проворачиваются диски, соответствующие более младшим разрядам числа, а потом — более старшим.

Например, пусть cейчас на счетчике написано число 18. Это значит, что на первом диске установлена цифра 0, на втором — 1, на третьем — 8. Следующее число после 18 — 19, поэтому при нажатии кнопки третий диск провернется на одно число, чтобы на нем оказалось установлена цифра 9, а остальные останутся неподвижными. Теперь на счетчике будет написано 19. После еще одного нажатия на счетчике должно будет оказаться число 20. Это значит, что третий диск должен про- вернуться на одно число, чтобы на нем оказалось установлена цифра 0, и что второй диск тоже должен провернуться, чтобы на нем оказалась установлена 2.

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

Входные данные
Вводится одно целое число n: сколько щелчков насчитал дядя Фёдор (0<=n<=1107).

Выходные данные
Выведите одной целое число: количество пролетевших мимо окна ворон. Если же дядя Фёдор ошибся, и такое количество щелчков не могло прозвучать, выведите −1.

Примеры

№	Входные данные	Выходные данные
1	9	9
2	10	-1

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

Входные данные
В первой строке записаны два числа N и M (1<=M<=N<=1000) – количество домов в Простоквашино и количество тех домов, которые ещё пользуются услугами почтальона Печкина, соответственно. Во второй строке записано M чисел ai , (1<=a_i<=N) возрастающем порядке – номера домов, которые ещё используют бумажную почту.

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

Примеры

№	Входные данные	Выходные данные	Пояснения
1	8 5 1 2 4 5 8	1	В приведенном примере дому, который имел номер 8, нужно дать номер 3. Тогда 5 домов, которые ещё используют бумажную почту, как раз будут иметь номера от 1 до 5.

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

Картофельные поля обычно очень аккуратно устроены: кусты картофеля рассажены на них так, что образуют клетчатое поле, где каждая клетка — картофельный куст. Как только на каком-то из кустов появляется колорадский жук, он начинает активно есть и размножаться. Поэтому каждый час на каждый куст будет добавляться столько же жуков, сколько соседних с ним по стороне кустов, уже зараженных жуками. Например, если у куста ровно один сосед, на котором уже есть жуки, то на него добавится один жук, а если все четыре соседа заражены жуками, то на куст добавится четыре новых жука. И если жуков не остановить, они заполнят собой все поле. Но к счастью, когда-то давно дядя Фёдор, прочитав статью в «Мурзилке», сделал отпугиватель колорадских жуков...

Если честно, Матроскин не очень понял, как работает этот отпугиватель. Но главное он запомнил: его надо установить на один из кустиков картофеля, и как только на этом кустике окажется ровно k колорадских жуков, что-то (вот этого Матроскин и не понял) произойдет и все жуки сбегут с поля.

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

Входные данные
Вам даны три числа: x и y — координаты кустика картофеля, на который Матроскин установил отпугиватель, и k — параметр отпугивателя (1<=k<=10⁹, |x|<=10⁹, |y|<=10⁹  ). Тот из кустов, на котором был найден первый жук, имеет координаты (0, 0) . Координаты всех кустов поля не превосходят 10⁹+1 по модулю.

Выходные данные
Выведите одно целое число: через сколько часов ловушка сработает. Если же ловушка никогда не сработает, выведите −1.

Примеры

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

Недавно дядя Фёдор прочитал в журнале «Мурзилка», что самый высокий водопад в мире — это водопад Анхель, высота которого составляет 1054 метра. «Вот было бы здорово посмотреть на такой водопад!», — размечтался он.

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

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

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

Теперь дяде Фёдору стало интересно, а какова высота самого высокого каскада водопадов на Сметанке? Помогите ему: по описанию реки, сделанному Шариком и дядей Фёдором, найдите это число.

Входные данные
В первой строке вводится число n (2<=n<=10⁵ ) — количество вершин ломаной, описывающей речку Сметанку. В следующих n строках перечислены координаты этих точек, в i-й строчке записаны числа x_i и y_i — расстояние от точки до истока по горизонтали и высота точки над уровнем моря (0x_i<=10⁹, y_i<=10⁹ ). Точки перечислены начиная от истока реки, то есть начиная с точки, x-координата которой равна нулю, а y-координата — максимальная среди всех точек. Гарантируется, что река течет сверху вниз и слева направо, то есть каждая следующая точка находится не выше и не левее предыдущей.

Выходные данные
Выведите одно целое число: высоту самого высокого каскада водопадов на этой реке. Если на реке на самом деле нет водопадов, выведите 0.

Примеры

№	Входные данные	Выходные данные
1	3 0 15 1 10 5 5	10

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

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

Дело в том, что на улице, которая отделяет Максима от остановки, меняют асфальт. Старый слой асфальта уже сняли (там теперь ямы, поэтому пройти там невозможно), и теперь по улице, приближаясь к Максиму, со скоростью 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

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

Входные данные
В первой строчке дано число N (1 ≤ N ≤ 200) — количество машин в пробке. В следующих N строчках записано по одному целому числу в каждой, причем в i-й строчке записана скорость i-й машины. Скорость каждой из машин не превышает 300. Считается, что (i + 1)-я машина едет за i-й, а первая машина может ехать со своей максимальной скоростью.

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

Примеры

№	Входные данные	Выходные данные
1	2 80 100	80 80

Ваня не очень-то любит людей, но, к сожалению, ему иногда все-таки приходится ездить на метро. В таких случаях ему помогают две вещи: наушники с любимыми «Scoprions» и правильно выбранное место. Поскольку Ваня хочет быть как можно дальше от всех людей, правильным местом считается такое место, расстояние от которого до ближайшего из соседей будет максимально возможным в вагоне. В вагоне N мест и они все расположены вдоль одной стены, причем вход в вагон находится у места с номером 1. Места идут подряд, без пропусков. Ваня понимает, что иногда правильных мест может быть несколько, и хочет сесть на ближайшее ко входу правильное место (то есть правильное место с минимальным номером).

Угадайте, какое место в вагоне займет Ваня.

Входные данные
В первой строке записано число N (1 ≤ N ≤ 105). В следующей строке через пробел записаны N чисел — 0 или 1. Число 0 обозначает свободное место, 1 — занятое; места нумеруются слева направо. Гарантируется, что хотя бы одно место свободно.

Выходные данные
Выведите номер места, на которое Ваня сядет.

Примеры

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

У Славы очень много друзей, и ему очень нравится с ними встречаться. Но, к сожалению, все друзья Славы живут в разных городах (каждый в своем), до которых Слава из своего Большого Города может добраться только на электричках. Каждый раз, когда Слава решает навестить кого-нибудь из своих друзей, перед ним встает нелегкий выбор — к кому же именно поехать на этот раз. Всех своих друзей Слава очень любит и не хочет никого обидеть. Поэтому он поступает следующим образом: в некоторый момент времени Слава выходит из дома и едет на вокзал. После приезда на вокзал Слава садится в ближайшую электричку, которая едет к одному из его друзей. По известному времени приезда Славы на вокзал помогите ему узнать, к какому именно другу он сегодня поедет.

Входные данные
В первой строке входных данных содержатся числа M (1 ≤ M ≤ 10⁵) — количество электричек, которые отправляются с вокзала, и время T, в которое Слава приезжает на вокзал (0 ≤ T ≤ 10⁹). Далее следует M строк, в каждой из которых содержится два числа t_i (0 ≤ t_i ≤ 10⁹, все ti различны) и fi (1 ≤ f_i ≤ 10⁹), где t_i — время отправления i-й электрички(все t_i различны), а f_i соответствует номеру друга, к которому идет i-я электричка. Гарантируется, что есть хотя бы одна электричка, которая отправляется позже, чем момент времени T.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 74 28 3 85 2 6 1 5 3 72 1	2	Считается, что Слава успевает на i-ю электричку только в том случае, если он приезжает раньше момента её отправления, т. е. T < ti.

В числе подсчитали количество единиц, в получившемся опять подсчитали количество единици т.д.
Например: 111211121112111 - 12 - 1 - 1 - 1 - ...

В итоге полученная последовательность стабилизировалась. На каком числе?

Например, последовательность 111211121112111 - 12 - 1 - 1 - 1 - ... стабилизировалась на числе 1.

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

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

Примеры

№	Входные данные	Выходные данные
1	12345	1
2	2007	0

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

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

Например, они сказали 1, 1, 1, 2. Следовательно, заведомо солгал 1 игрок. (Какие-то трое могли сказать правду, но все четверо правду сказать не могли, так как тузов всего 4).

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

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

Примеры

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

Представьте число 2011 в виду суммы K последовательных простых чисел (то есть простых чисел, между которыми нет других простых чисел). Например, число 31 можно представить в виде суммы трех посдедовательных простых чисел следующим образом: 7 + 11 + 13 = 31.

Входные данные
Вводится одно натуральное число K (от 1 до 2011).

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

Если разложить в сумму K слагаемых невозможно, выведите NO SOLUTION (заглавными буквами).

Примеры

№	Входные данные	Выходные данные
1	3	661 673 677
2	2	NO SOLUTION

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	abcdefg abd	NO
2	abcdg bag	YES
3	a aaa	YES

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

Входные данные
В первой строке вводится одно натуральное число N, не превосходящее 100.

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

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

Если решений несколько, выведите любое из них.

Если решений нет, выведите фразу NO SOLUTION (заглавными буквами).

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

Примеры

№	Входные данные	Выходные данные
1	3 5 5 5	NO SOLUTION
2	4 1 2 3 8	1 2 3 1

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	1 2 3 4 5	(1) 2 3 4 (5) = 9
2	10 11 10 11 10	(10) 11 10 (11) 10 = 31

Вася давно мечтает выиграть олимпиаду по информатике. У него всего три слабых места: циклы, массивы и строки. Перед сегодняшним турниром Вася провёл интенсивную подготовку, в ходе которой он решил A задач на циклы, B задач на массивы и C задач на строки. Впоследствии выяснилось, что из решённых задач D были и на циклы, и на массивы, E – на циклы и на строки, F – на строки и на массивы. И даже было G задач, которые включали и циклы, и строки, и массивы. Помогите Васе вычислить, сколько всего различных задач он решил.

Входные данные
Вводятся числа A, B, C, D, E, F и G, разделенные пробелами.
Во всех тестовых примерах все входные данные корректны и не превосходят 1 000. Числа могут быть равны нулю.

Выходные данные
Выведите одно число – число задач, решенных Васей.
 
 

Примеры

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

Натуральные числа записаны в (бесконечную) таблицу, как показано на рисунке.


Требуется по заданному числу вывести всех его соседей (числа, записанные в клетках сверху, справа, слева и снизу, если таковые имеются)

Входные данные
Вводится одно натуральное число, не превосходящее 10⁹.

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

Примеры

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

Решите в целых числах уравнение:

\( { \sqrt{ax +b}} = c\)

a, b, c – данные целые числа: найдите все решения или сообщите, что решений в целых числах нет.

Входные данные
Вводятся три числа a, b и c, разделенные пробелами.

Выходные данные
Программа должна вывести все решения уравнения в порядке возрастания, либо NO SOLUTION (заглавными буквами), если решений нет. Если решений бесконечно много, вывести MANY SOLUTIONS. 

Примеры

№	Входные данные	Выходные данные
1	1 0 0	0
2	1 2 -3	NO SOLUTION

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

Входные данные
Сначала на вход программы поступает текст, введенный Васей – одна строка из не более чем 100 латинских строчных букв. В следующей строке входных данных задается значение N – количество слов в словаре (N – натуральное число, не превосходящее 2000). В следующих N строках записаны слова из словаря – по одному слову в  строке, каждое слово содержит не более 20 латинских строчных букв. Слова записаны в алфавитном порядке.


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

Примеры

№	Входные данные	Выходные данные
1	whatcanido 6 a an can do i what	what can i do

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

Входные данные
Сначала вводится одно целое число N (0 < N ≤ 1000).

В каждой из следующих N строк через пробел расположены 4 целых числа, первые два из которых обозначают время открытия кассы в часах и минутах (часы — целое число от 0 до 23, минуты — целое число от 0 до 59), оставшиеся два — время закрытия в том же формате. Числа разделены пробелами.

Время открытия означает, что в соответствующую ему минуту касса уже работает, а время закрытия — что в соответствующую минуту касса уже не работает. Например, касса, открытая с 10 ч. 30 мин. до 18 ч. 30 мин., ежесуточно работает 480 минут.

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

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

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 1 0 23 0 12 0 12 0 22 0 2 0	120	Первая касса работает с часу до 23 часов, вторая – круглосуточно, третья – с 22 часов до 2 часов ночи следующего дня. Таким образом, все три кассы одновременно работают с 22 до 23 часов и с часу до двух часов, то есть 120 минут.
2	2 9 30 14 0 14 15 21 0	0	Первая касса работает до 14 часов, а вторая начинает работать в 14 часов 15 минут, то есть одновременно кассы не работают.
3	2 14 00 18 00 10 00 14 01	1	Вместе кассы работают лишь одну минуту – с 14:00 до 14:01 (в 14:01 вторая касса уже не работает).