Когда программист Вова был в Китае, он обнаружил, что российские часы «Заря» продаются там в десять раз дешевле, чем в России. Вова решил провернуть выгодное дело и закупил огромную партию, с тем чтобы привезти часы на родину и продать их за полцены (то есть, впятеро дороже, чем купил). Но дома обнаружилось, что многие часы идут вразнобой, к тому же, от малейшего толчка часы останавливаются (либо наоборот, начинают идти). Очевидно, это были не настоящие часы фирмы «Заря», а их точные копии… Чтобы быстро продать всю партию часов, Вова хочет поставить их все на одинаковое время (тогда будет неважно, правильное это время или нет — можно будет сказать, что это местное время завода-изготовителя) и перед открыванием крышки просто встряхнуть чемодан, чтобы часы одновременно пошли.
Для установки времени на часах есть заводная головка, вращение которой позволяет
быстро поворачивать стрелки, при этом часовая стрелка крутится в 12 раз медленнее минутной, а минутная — в 60 раз медленнее секундной. Один оборот заводной головки поворачивает секундную стрелку на полный оборот, и хотя на такой поворот уходит всего одна секунда, чтобы изменить время на 6 часов, потребуется 6 минут. Вращать заводную головку и стрелки можно только по часовой стрелке, чтобы не повредить хрупкий механизм часов. Помогите Вове минимизировать усилия по предпродажной подготовке часов, выбрав время, которое будет установлено на всех часах.
Исходные данные
В первой строке содержится одно целое число n (1 ≤ n ≤ 50000) — количество часов в партии. Далее следует n строк, (i+1)-я строка ввода содержит время на i-х часах в формате h:mm:ss, где целое число h (1 ≤ h ≤ 12) означает час, а двухразрядные целые числа mm и ss (00 ≤ mm, ss ≤ 59) — минуты и секунды соответственно.
Результат
Выведите время, которое нужно установить на всех часах, в формате, указанном выше.
Пример
исходные данные | результат |
---|
3
11:30:00
12:10:01
6:10:18
| 12:10:01
|
Автор задачи: Андрей Демидов
Источник задачи: ACM ICPC 2007–2008. NEERC. Восточный подрегион. Екатеринбург, 27 октября 2007 г.