Meeting arrangement P97291

[r]

Arranging a meeting on a company that has branches all over the world is difficult, as employees might need to stay up until late or wake up early to attend those meetings. Sometimes this even forces them to reschedule their vital cycle. Since this results in underperformance, the company has hired you to determine which is the best time to schedule a worldwide meeting.

All employees will reschedule their sleep so that they go to the meeting right after lunch (this way they have an excuse to take a nap during the meeting). Suppose that we know, for everybody, the UTC time at which he or she currently finishes lunch. Our objective is to compute the minimum possible sum of individual displacements (in absolute time).

Consider the first case of the sample. If we arrange a meeting at 08:00:00 UTC, then the first employee has to move forward his biological clock 4 hours (moving it back 20 hours is a worse option), while the second employee has to move it back 3 hours, 59 minutes and 59 seconds. Therefore, the total sum of displacements for a meeting at 08:00:00 UTC is 7 hours, 59 minutes and 59 seconds, which is optimal for this case.

Input

Input consists of several cases. Every case begins with the number of employees n. Then follow the UTC lunch time of each of the n employees in nondescending order, in the format HH:MM:SS. Assume 0 ≤ n ≤ 10⁵, 00 ≤ HH ≤ 23, 00 ≤ MM ≤ 59, and 00 ≤ SS ≤ 59.

Output

For every case, print the minimum sum of displacements in the format HH:MM:SS. If the number of hours exceeds 99, print all its digits.