Зупинені годинники
Посеред Тірренського моря розташований невеликий вулканічний острів Хронус. Хоча зараз він безлюдний, колись тут існувала цивілізація. Історичні записи свідчать, що острів був знищений виверженням вулкана приблизно 800 років тому, і більшість мешканців загинули від пірокластичних потоків, спричинених вулканічною активністю. У 2003 році європейська команда археологів розпочала розкопки на острові Хронус. З того часу проект приніс багато важливих історичних відкриттів. Зокрема, влітку 2008 року команда знайшла кілька механічних годинників, які носили жертви катастрофи. Це свідчить про те, що жителі острова Хронус володіли високорозвиненими технологіями.
Після розкопок годинників археологи намагалися визначити час доби, коли сталася катастрофа, але зіткнулися з кількома труднощами. По-перше, надзвичайна спека пірокластичних потоків сильно пошкодила годинники, стерши літери та цифри на них. По-друге, кожен годинник має ідеально круглу форму, тому важко визначити, де верх годинника. Нарешті, хоча кожен годинник має три стрілки, вони виглядають однаково, тому не можна сказати, яка з них годинна, хвилинна чи секундна (це загадка, як жителі острова Хронус розрізняли стрілки. Деякі археологи припускають, що стрілки могли бути пофарбовані в різні кольори, але це лише гіпотеза, оскільки фарба зникла через спеку). Це означає, що ми не можемо однозначно визначити час, вказаний годинником; може бути кілька можливих варіантів. Ми повинні розглянути різні обертання годинника. Крім того, оскільки існує кілька можливих інтерпретацій стрілок, ми також повинні розглянути всі перестановки стрілок.
Ви є інформаційним археологом, запрошеним до команди проекту, і вас просять визначити найбільш ймовірний часовий інтервал, протягом якого сталася катастрофа, з набору розкопаних годинників.
Далі ми виражаємо час за модулем 12 годин. Ми записуємо час у форматі hh:mm:ss, де hh, mm та ss позначають годину (hh = 00, 01, 02, ..., 11), хвилину (mm = 00, 01, 02, ..., 59) та секунду (ss = 00, 01, 02, ..., 59) відповідно. Час починається з 00:00:00 і збільшується кожну секунду 00:00:00, 00:00:01, 00:00:02, ..., але повертається до 00:00:00 кожні 12 годин.
Годинники на острові Хронус дотримуються наступних умов сучасних аналогових годинників.
Годинник має три стрілки: годинну, хвилинну та секундну, хоча вони виглядають однаково, як зазначено вище.
Кожна стрілка рухається на 6 градусів за годинниковою стрілкою дискретно. Тобто жодна стрілка не залишається між поділками, і кожна стрілка повертається в те саме положення кожні 60 поділок.
Секундна стрілка рухається кожну секунду.
Хвилинна стрілка рухається кожні 60 секунд.
Годинна стрілка рухається кожні 12 хвилин.
У момент 00:00:00 всі три стрілки знаходяться в одному положенні.
Оскільки жителі острова Хронус були досить уважні, щоб підтримувати свої годинники в правильному стані, і пірокластичні потоки швидко поширювалися по острову, можна припустити, що всі годинники зупинилися в короткому проміжку часу. Тому дуже ймовірно, що час, коли сталася катастрофа, знаходиться в найкоротшому часовому інтервалі, протягом якого всі розкопані годинники мають принаймні один кандидатський час.
Ви повинні обчислити найкоротший часовий інтервал і повідомити про це команді проекту.
Вхідні дані
Вхід складається з кількох наборів даних, кожен з яких має наступний формат.
n
s_1 t_1 u_1
s_2 t_2 u_2
...
s_n t_n u_n
Перший рядок містить одне ціле число n (2 ≤ n ≤ 10), що представляє кількість годинників. Три числа s_i, t_i, u_i в кожному рядку є цілими числами, такими що 0 ≤ s_i, t_i, u_i ≤ 59 і вони вказують положення трьох стрілок за кількістю поділок відносно довільно обраного положення.
Зверніть увагу, що положення стрілок годинника можна виразити багатьма різними способами. Наприклад, якщо годинник зупинився на часі 11:55:03, положення стрілок можна виразити по-різному, обертаючи годинник довільно (наприклад, 59 55 3, 0 56 4, 1 57 5 тощо) і також переставляючи годинну, хвилинну та секундну стрілки довільно (наприклад, 55 59 3, 55 3 59, 3 55 59 тощо).
Кінець вводу позначається рядком, що містить один нуль.
Вихідні дані
Для кожного набору даних виведіть найкоротший часовий інтервал, протягом якого всі годинники, наведені в наборі даних, мають принаймні один кандидатський час. Вивід має бути записаний в одному рядку у наступному форматі для кожного набору даних.
hh:mm:ss h′h′:m′m′:s′s′
Кожен рядок містить пару часів hh:mm:ss та h′h′:m′m′:s′s′, що вказують, що найкоротший інтервал починається о hh:mm:ss і закінчується о h′h′:m′m′:s′s′ включно. Початковий час і кінцевий час розділені одним пробілом, і кожен з них повинен складатися з години, хвилини та секунди у двох цифрах, розділених двокрапками. Жодні зайві символи не повинні з'являтися у виводі.
При обчисленні найкоротшого інтервалу ви можете скористатися тим, що кожен годинник має принаймні один кандидатський час і що найкоротший часовий інтервал містить 00:00:00 лише якщо інтервал починається з 00:00:00 (тобто найкоротший інтервал закінчується до того, як час повертається до 00:00:00).
Якщо існує більше одного часового інтервалу, що дає найкоротший, виведіть той, що першим настає після 00:00:00 включно.