The tramway is one of the attractions of Hong Kong. It is served by
double-decker trams of 1940 – 50s with wooden seats. The trams
run strictly on schedule, so that the residents of the homes along the
tram line can check their watches by the rumble of trams passing by.
The Shau Kei Wan – Sheung Wan route trams go past the hotel where Vova stopped.
Yesterday Vova bought a bag of rare Chinese coins on the market, so he
has spent the whole day today in the hotel room, sorting the coins by year and
value. During the day trams went along the street a few times. The sound
of a tram gives the exact time when the tram passes the hotel but it is
impossible to determine in which direction the tram is going at this
moment. Vova wrote all moments when trams went past his hotel in his
notebook and he now wants use this data to make a tram schedule. Help him
to do this.
The speed of a tram is constant and equal for all trams. The time the tram
needs to stop at tram stops and stations should be neglected. All
trams make the same number of cycles in a day, one cycle is the route:
Shau Kei Wan – Sheung Wan – Shau Kei Wan. The first tram leaves from the Shau Kei Wan
station not earlier than 00:00:00, the last tram comes back there no later
than 23:59:59. The last tram leaves from the Shau Kei Wan station before the
first tram finishes its first cycle. A tram needs a positive integer
number of seconds to get from Vova's hotel to any of the two tram
stations. No two trams passed the hotel at the same time.
The first line contains the time the first tram left from the Shau Kei Wan
station. Next n lines contain the moments of time when the trams passed
Vova's hotel (2 ≤ n ≤ 5 000; n is even). Time is always given
in the “hh:mm:ss” format and is between 00:00:00 and 23:59:58. The times
when the trams passed the hotel are distinct and sorted in the ascending
order. The time the first tram left from the the Shau Kei Wan station is
strictly less than the time this tram first passed the hotel.
For each tram you need to print a single line containing the times this
tram passed the terminal stations (Shau Kei Wan and Sheung Wan) in the increasing order in the
format “hh:mm:ss”. First, you should print a line describing the tram
that started going first. Second, you should print a line describing the
tram that started going second and so on. If there are multiple solutions,
you may print any of them. It is guaranteed that at least one
08:00:00 08:23:00 08:46:00 09:09:00 09:32:00
08:37:19 09:00:19 09:23:19 09:46:19 10:09:19
08:44:02 09:07:02 09:30:02 09:53:02 10:16:02
Problem Source: Open Ural FU Personal Contest 2013