ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

NEERC 2011, Четвертьфинал Восточного подрегиона

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

H. Утро в Кольцово

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Воскресное утро 30 октября надолго запомнится диспетчерам аэропорта Кольцово. С рассветом на взлётно-посадочную полосу один за другим начнут выруливать самолёты, на которых отправятся домой участники завершившегося в Екатеринбурге четвертьфинала чемпионата мира по программированию. Более того, один за другим на посадку будут заходить новейшие авиалайнеры компании Oceanic Airlines, которая решила организовать в Кольцово выставку своих самолётов. Как же справиться с таким потоком, ведь в настоящий момент времени в Кольцово функционирует только одна взлётно-посадочная полоса?
Когда посадка в самолёт заканчивается, он отчаливает от аэровокзала и встаёт в очередь на взлёт. Когда прибывающий самолёт оказывается в близости от аэропорта, он встаёт в очередь на посадку. Самолёт начинает взлёт или посадку, как только получает соответствующее разрешение от диспетчеров. Диспетчеры не дадут разрешения на взлёт, пока в очереди на посадку будут находиться самолёты, независимо от того, получили ли они разрешение на посадку или ещё нет. Если один самолёт становится в очередь на посадку в тот момент, когда другой готов начать взлёт, то второй самолёт не получит разрешения на взлёт, пока не сядет первый.
Из соображений безопасности между взлётами и посадками должен проходить определённый промежуток времени. После того как самолёт начнёт взлёт, должно пройти хотя бы t1 секунд, прежде чем другой самолёт сможет начать взлёт, и хотя бы t2 секунд, прежде чем другой самолёт сможет начать посадку. После того как один самолёт начал посадку, должно пройти хотя бы t3 секунд, прежде чем другой получит разрешение на взлёт, и хотя бы t4 секунд, прежде чем другой самолёт сможет начать посадку.
Для каждого самолёта вы знаете точное время, когда он встанет в очередь на взлёт или на посадку. Вычислите по этим данным, когда самолёты получат от диспетчеров разрешение взлететь или сесть соответственно.

Исходные данные

В первой строке записаны целые числа t1, t2, t3, t4 (30 ≤ ti ≤ 500; max(t1, t4) ≤ min(t2, t3)). Во второй строке записано целое число n — количество взлетающих самолётов (1 ≤ n ≤ 50). Следующие n строк содержат время, в которое эти самолёты встают в очередь на взлёт. В следующей строке записано целое число m — количество садящихся самолётов (1 ≤ m ≤ 50). Далее для каждого из них приведено время, в которое этот самолёт занимает место в очереди на посадку. Все времена даются в формате hh:mm:ss и лежат в диапазоне от шести до десяти часов утра. Времена в каждом списке попарно различны и упорядочены по возрастанию.

Результат

В первых n строках выведите время, в которое взлетающие самолёты получат разрешение диспетчеров на взлёт. В следующих m строках выведите время, в которое садящиеся самолёты получат разрешение на посадку. Время следует выводить в формате hh:mm:ss. Самолёты нужно описывать в том же порядке, в котором они даны на входе.

Пример

исходные данныерезультат
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
Автор задачи: Денис Дублённых
Источник задачи: NEERC 2011, Четвертьфинал Восточного подрегиона
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1892. Утро в Кольцово