Several students wake up in the morning and want to drink a cup of hot coffee. But they have only one teakettle. In this case, they usually operate according the following instruction:
Students should wake up one after another and act as follows:
- If, when a student wakes up, nobody boils the water, he should fill the teaketle with 200 ml of water and put it on the burner. Water has initial temperature 20 °C.
- If another student boils water already, he should add 200 ml of water in the teakettle. As a result, water temperature equalize according to law T = (m1T1 + m2T2) / (m1 + m2), where m1, m2 – mass of water in teakettle and mass of additional portion of water, and T1, T2 – their temperatures.
- If another students boil water and the teakettle is full already then other students should wait until the teakettle becomes free. The teakettle capacity is 1 liter (1 kg) of water i.e. 5 students are able to boil water simultaneously.
- As soon as water begins to boil, i.e. the water temperature runs up to 100 °C, the teakettle should be put off the burner and water should be poured into the cups, 200 ml for each student. At the same moment teakettle can be used for boiling next portion of water. Water heats up by ΔT = (P Δt) / (C m) degrees during Δt seconds, where P – is a power of burner, C = 4190 J/kg·K – specific heat of water, m – water mass.
You are giver wake up time for each student and you are to simulate this process to find for each student the time when he will be able to drink a cup of coffee. Assume, that students can perform described manipulations in a moment. Power of burner P = 400 Watt.
The first line of input contains single integer N – amount of students (0 ≤ N ≤ 500). Each of the following N lines contains a wake up time of corresponding student in format HH:MM:SS. Times are sorted in ascending order. All students wake up at the different moments but during the same day, i.e. all times different and between 00:00:00 and 23:59:59.
For each student you should output the time when he will be able to drink his coffee in the same format HH:MM:SS.
Problem Author: Vladimir Yakovlev
Problem Source: USU Junior Championship March'2005