print2096. Перелет

printПерелет

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Далеко не во всех больших странах хорошо развита внутренняя авиация. Так, иногда, чтобы попасть из одного большого города в другой, приходится делать это двумя рейсами с пересадкой в столице. Зато в таких странах обычно не возникает проблем с попаданием из любого города в столицу и из столицы куда угодно.
Итак, вы разрабатываете систему бронирования авиабилетов. Конкретно сейчас вам необходимо реализовать ту ее часть, которая по списку рейсов из города А в столицу страны и списку рейсов из столицы в город В выведет самый дешевый способ попасть из города А в город В. При этом важно, что на стыковку должно быть заложено не меньше 15 минут. То есть, если пассажир приземлился в столице в 23:00:00, то на рейс в В в 23:15:00 он успеет, а на рейс в 23:14:59 – нет.
В случае, если существует несколько вариантов с одинаковой суммарной ценой, и эта цена минимальна, выведите тот вариант, в котором меньше время прибытия в В. Если существует несколько таких вариантов – выведите любой из них.
Первая строка входного файла содержит одно натуральное число `n` (`1\ ≤\ n\ ≤\ 100\ 000`) – количество рейсов из города А в столицу государства. В следующих `n` строках описаны эти рейсы. Описание рейса состоит из его номера, времени вылета, времени прилета и цены билета на этот рейс, разделенных пробелами. Номер рейса – набор заглавных латинских букв и цифр длиной не более пяти символов. Времена описаны в формате `"hh":"mm":"ss"`. Гарантируется, что для любого рейса время прибытия больше, чем время вылета. Цена билета – натуральное число, не превышающее `100\ 000`.
Следующая строка входного файла содержит одно натуральное число `m` (`1\ ≤\ m\ ≤\ 100\ 000`) – количество рейсов из столицы в город В. В следующих `m` строках описаны рейсы в В в формате, аналогичном описанному выше.
Гарантируется, что не существует двух рейсов с одинаковыми номерами.
В первой строке выведите номер рейса, которым пассажир полетит в столицу. Во второй – номер рейса, которым он полетит из столицы в город В. При этом в городе В пассажир должен оказаться в те же сутки, в которые он вылетел из города А, то есть переход через сутки во время ожидания стыковки невозможен.

Пример ввода

3
UT135 08:00:00 11:00:00 1350
FV42 09:00:00 10:50:00 1500
A123B 12:00:15 16:50:38 2000
3
PK074 17:30:00 23:00:00 1350
NV074 11:04:59 22:59:00 1100
AK59 10:00:00 19:00:00 200

Пример вывода

UT135
PK074
Источник: neerc.ifmo.ru/school
loading