Stopped Watches

In the middle of the Tyrrhenian Sea lies a small volcanic island called Chronus. It is uninhabited now, but it was once a civilized island. Historical records suggest that about 800 years ago a volcanic eruption annihilated the island and that pyroclastic flows killed most of its people. In 2003 a European team of archaeologists began an excavation on Chronus Island, and it has since revealed many significant historical insights. In particular, the discovery made in the summer of 2008 astonished the world: the team excavated several mechanical watches worn by the victims of the disaster. This shows that the islanders had a highly advanced manufacturing technology.

Shortly after excavating the watches, the archaeologists tried to determine at what time of day the disaster happened, but they failed for several reasons. First, the extreme heat of the pyroclastic flows severely damaged the watches and erased the printed letters and numbers. Second, every watch is a perfect circle, so one cannot tell where its top is. Third, each watch has three hands that look completely identical, so one cannot tell which is the hour, the minute, or the second hand.¹ This means the time indicated by a watch cannot be determined uniquely; there can be several candidates, because we must consider every rotation of the watch and every permutation of the three hands.

You are an information archaeologist invited to the team, asked to infer the most plausible time interval within which the disaster happened from the set of excavated watches.

Times are expressed modulo 12 hours, written as hh:mm:ss, where $hh$ is the hour ($hh = 00, 01, \dots, 11$), $mm$ is the minute ($mm = 00, 01, \dots, 59$), and $ss$ is the second ($ss = 00, 01, \dots, 59$). Time starts at 00:00:00 and counts up every second as 00:00:00, 00:00:01, 00:00:02, \dots, reverting to 00:00:00 every 12 hours.

The watches obey the following conventions of modern analog watches.

• A watch has three hands (hour, minute, and second), though they look identical as noted above.
• Every hand ticks $6°$ clockwise in a discrete manner: no hand ever rests between ticks, and each hand returns to the same position after 60 ticks.
• The second hand ticks every second.
• The minute hand ticks every 60 seconds.
• The hour hand ticks every 12 minutes.

At 00:00:00 all three hands are at the same position.

Because the islanders kept their watches reasonably accurate and the pyroclastic flows spread very quickly, we may assume all the watches stopped within a short interval. Hence the disaster time is expected to lie in the shortest time interval within which every excavated watch has at least one candidate time.

Compute that shortest time interval and report it to the team.

The input consists of multiple datasets, each formatted as follows.

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

The first line contains a single integer $n$ ($2 \le n \le 10$), the number of watches. On each following line the three integers $s_i, t_i, u_i$ satisfy $0 \le s_i, t_i, u_i \le 59$ and give the positions of the three hands, in ticks, relative to an arbitrarily chosen reference position.

Note that a watch's hand positions can be written in many ways. For example, if a watch stopped at 11:55:03, its positions can be written differently by rotating the watch (e.g. 59 55 3, 0 56 4, 1 57 5) and by permuting the hour, minute, and second hands (e.g. 55 59 3, 55 3 59, 3 55 59).

The end of the input is indicated by a line containing a single 0.

For each dataset, output on one line the shortest time interval within which every watch in that dataset has at least one candidate time, in the following format.

hh:mm:ss h′h′:m′m′:s′s′

Each line contains a pair of times hh:mm:ss and h′h′:m′m′:s′s′, meaning the shortest interval begins at hh:mm:ss and ends at h′h′:m′m′:s′s′ inclusive. The beginning and ending times are separated by a single space, and each consists of two-digit hour, minute, and second joined by colons. No other characters appear in the output.

In computing the shortest interval you may rely on these facts: every watch has at least one candidate time, and the shortest interval contains 00:00:00 only if it starts at 00:00:00 (that is, the shortest interval ends before time reverts to 00:00:00).

If more than one interval is shortest, output the one that comes first after 00:00:00 inclusive.