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
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
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.
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
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
hh:mm:ss. The planes should be described in the same order in
which they are given in the input.
60 60 60 60
Problem Author: Denis Dublennykh
Problem Source: NEERC 2011, Eastern subregional contest