| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 5 | 5 | 1 | 100.000% |
Далеко не во всех больших странах хорошо развита внутренняя авиация. Так, иногда, чтобы попасть из одного большого города в другой, приходится делать это двумя рейсами с пересадкой в столице. Зато в таких странах обычно не возникает проблем с попаданием из любого города в столицу и из столицы куда угодно.
Итак, вы разрабатываете систему бронирования авиабилетов. Конкретно сейчас вам необходимо реализовать ту ее часть, которая по списку рейсов из города А в столицу страны и списку рейсов из столицы в город В выведет самый дешевый способ попасть из города А в город В. При этом важно, что на стыковку должно быть заложено не меньше 15 минут. То есть, если пассажир приземлился в столице в 23:00:00, то на рейс в В в 23:15:00 он успеет, а на рейс в 23:14:59 --- нет.
В случае, если существует несколько вариантов с одинаковой суммарной ценой, и эта цена минимальна, выведите тот вариант, в котором меньше время прибытия в В. Если существует несколько таких вариантов --- выведите любой из них.
Первая строка входного файла содержит одно натуральное число $n$ (1ドル \le n \le 100,000$) --- количество рейсов из города А в столицу государства. В следующих $n$ строках описаны эти рейсы. Описание рейса состоит из его номера, времени вылета, времени прилета и цены билета на этот рейс, разделенных пробелами. Номер рейса --- набор заглавных латинских букв и цифр длиной не более пяти символов. Времена описаны в формате hh:mm:ss. Гарантируется, что для любого рейса время прибытия больше, чем время вылета. Цена билета --- натуральное число, не превышающее 100,000ドル$.
Следующая строка входного файла содержит одно натуральное число $m$ (1ドル \le m \le 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