2096. Перелет

Далеко не во всех больших странах хорошо развита внутренняя авиация. Так, иногда, чтобы попасть из одного большого города в другой, приходится делать это двумя рейсами с пересадкой в столице. Зато в таких странах обычно не возникает проблем с попаданием из любого города в столицу и из столицы куда угодно.

Итак, вы разрабатываете систему бронирования авиабилетов. Конкретно сейчас вам необходимо реализовать ту ее часть, которая по списку рейсов из города А в столицу страны и списку рейсов из столицы в город В выведет самый дешевый способ попасть из города А в город В. При этом важно, что на стыковку должно быть заложено не меньше 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