멈춘 시계들

티레니아해 한가운데에는 크로누스라 불리는 작은 화산섬이 있다. 지금은 무인도이지만 한때는 문명을 이룬 섬이었다. 여러 역사 기록에 따르면 약 800년 전 화산 폭발로 섬이 파괴되었고, 화쇄류에 휩쓸려 대부분의 주민이 목숨을 잃었다고 한다. 2003년 한 유럽 발굴단이 크로누스섬에서 발굴을 시작했고, 그 뒤 많은 역사적 사실이 밝혀졌다. 특히 2008년 여름의 발견은 세상을 놀라게 했다. 발굴단이 재난 희생자들이 차고 있던 기계식 손목시계 여러 점을 발굴한 것이다. 이는 이 섬 사람들이 매우 발달한 제조 기술을 가지고 있었음을 보여 준다.

시계를 발굴한 직후, 발굴단은 재난이 하루 중 몇 시에 일어났는지 알아내려 했지만 몇 가지 어려움 때문에 실패했다. 첫째, 화쇄류의 극심한 열이 시계를 심하게 훼손해 문자와 숫자가 모두 지워졌다. 둘째, 모든 시계가 완전한 원형이라 어디가 위쪽인지 알 수 없다. 셋째, 세 개의 바늘이 모두 똑같이 생겨서 어느 것이 시침·분침·초침인지 구별할 수 없다.¹ 따라서 한 시계가 가리키는 시각을 하나로 정할 수 없고 여러 후보가 생긴다. 시계의 회전과 세 바늘의 모든 배치를 함께 고려해야 하기 때문이다.

당신은 이 발굴단에 초빙된 정보 고고학자로서, 발굴된 시계들로부터 재난이 일어났을 가장 그럴듯한 시간 구간을 추정하는 임무를 맡았다.

시각은 12시간을 주기로 나타낸다. 시각을 hh:mm:ss로 쓰며, 여기서 $hh$는 시($hh = 00, 01, \dots, 11$), $mm$은 분($mm = 00, 01, \dots, 59$), $ss$는 초($ss = 00, 01, \dots, 59$)를 뜻한다. 시각은 00:00:00에서 시작해 매초 00:00:00, 00:00:01, 00:00:02, \dots처럼 1씩 증가하고, 12시간마다 다시 00:00:00으로 돌아간다.

이 섬의 시계는 다음과 같은 현대 아날로그 시계의 규칙을 따른다.

• 시계에는 시침·분침·초침 세 개의 바늘이 있으나, 앞서 말했듯 셋의 모양이 완전히 같다.
• 모든 바늘은 시계 방향으로 한 번에 $6°$씩 불연속적으로 움직인다. 즉 바늘은 눈금 사이에 멈추지 않으며, 60번 움직이면 처음 위치로 돌아온다.
• 초침은 1초마다 한 눈금 움직인다.
• 분침은 60초마다 한 눈금 움직인다.
• 시침은 12분마다 한 눈금 움직인다.

00:00:00일 때 세 바늘은 모두 같은 위치에 있다.

이 섬 사람들은 시계를 꽤 정확하게 맞춰 두었고 화쇄류가 매우 빠르게 섬을 덮쳤으므로, 모든 시계는 짧은 시간 안에 멈췄다고 볼 수 있다. 따라서 재난이 일어난 시각은, 발굴된 모든 시계가 후보 시각을 적어도 하나씩 갖는 가장 짧은 시간 구간 안에 있다고 볼 수 있다.

그 가장 짧은 시간 구간을 구해 발굴단에 보고하라.

입력은 여러 개의 데이터셋으로 이루어지며, 각 데이터셋의 형식은 다음과 같다.

n
s1 t1 u1
s2 t2 u2
...
sn tn un

첫 줄에는 시계의 개수를 나타내는 정수 $n$($2 \le n \le 10$)이 주어진다. 이어지는 각 줄의 세 정수 $s_i, t_i, u_i$는 $0 \le s_i, t_i, u_i \le 59$를 만족하며, 임의로 정한 기준 위치로부터 세 바늘의 위치를 눈금 수로 나타낸 값이다.

한 시계의 바늘 위치는 여러 방식으로 표현될 수 있음에 유의하라. 예를 들어 어떤 시계가 11:55:03에 멈췄다면, 시계를 임의로 회전시켜 위치를 다르게 적을 수 있고(예: 59 55 3, 0 56 4, 1 57 5 등), 시침·분침·초침을 임의로 뒤바꿔 적을 수도 있다(예: 55 59 3, 55 3 59, 3 55 59 등).

입력의 끝은 0 하나만 있는 줄로 나타낸다.

각 데이터셋에 대해, 해당 데이터셋의 모든 시계가 후보 시각을 적어도 하나씩 갖는 가장 짧은 시간 구간을 한 줄에 다음 형식으로 출력한다.

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(포함)에서부터 가장 먼저 오는 구간을 출력한다.