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

1892. Morning in Koltsovo

Time limit: 1.0 second
Memory limit: 64 MB
Air traffic controllers at Koltsovo airport will long remember the Sunday morning of October 30. At dawn, the planes carrying participants of the Eastern Subregional Contest back home will start taxiing onto the runway one after another. At the same time, newest airplanes of the Oceanic Airlines company will be landing one after another to take part in the exhibition of the company fleet, which will be held in Koltsovo. The airport has only one operating runway, so managing this flow of airplanes might be a difficult problem for the air traffic controllers.
When all the passengers are aboard a plane, it taxis away from the terminal and queues for takeoff. When a plane is arriving to the airport, it queues for landing. A plane starts takeoff or landing as soon as it receives the corresponding clearance from the air traffic controllers. A plane is not cleared for takeoff as long as there are planes queued for landing regardless of whether they are cleared for landing or not. If a plane queues for landing at the same moment when another plane is ready for takeoff, then the latter plane will not be cleared for takeoff until the former plane lands.
For safety reasons, a certain time must pass between takeoffs and landings. After a plane starts takeoff, at least t1 seconds must pass before another plane is cleared for takeoff and at least t2 seconds must pass before another plane is cleared for landing. After a plane starts landing, at least t3 seconds must pass before another plane is cleared for takeoff and at least t4 seconds must pass before another plane is cleared for landing.
For each plane you know the exact time when this plane queues for takeoff or landing. Use these data to calculate the times when the planes will be cleared for takeoff or landing, respectively.

Input

The first line contains the integers t1, t2, t3, and t4 (30 ≤ ti ≤ 500; max(t1, t4) ≤ min(t2, t3)). In the second line you are given the number of departing planes n (1 ≤ n ≤ 50). The following n lines contain the times when each plane queues for takeoff. In the next line you are given the number of arriving planes m (1 ≤ m ≤ 50). Then there are the times when each of them queues for landing. All the times are in the format hh:mm:ss and are in the range from 6 a.m. to 10 a.m. The times in each list are pairwise different and are given in ascending order.

Output

In the first n lines output the times when the departing planes will be cleared for takeoff. In the following m lines output the times when the arriving planes will be cleared for landing. The times should be output in the format hh:mm:ss. The planes should be described in the same order in which they are given in the input.

Sample

inputoutput
60 60 60 60
2
07:01:00
07:01:30
2
07:00:00
07:02:10
07:01:00
07:02:00
07:00:00
07:03:00
Problem Author: Denis Dublennykh
Problem Source: NEERC 2011, Eastern subregional contest