Остановленные часы
Посреди Тирренского моря находится небольшой вулканический остров под названием Хронус. Сейчас он необитаем, но когда-то здесь процветала цивилизация. Исторические записи предполагают, что остров был уничтожен извержением вулкана около 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 включительно.