ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1969. Hong Kong Tram

Time limit: 1.0 second
Memory limit: 64 MB
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 solution exists.


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