Город Летовецк славится своими туристическими маршрутами. Каждый маршрут проходит через несколько достопримечательностей. Многие туристы желают посетить город, но не у всех хватает времени увидеть все достопримечательности. Туристам предлагают составить список достопримечательностей, которые они бы хотели посетить. Турагент в ответ выбирает для них самый короткий маршрут, включающий все выбранные достопримечательности.
В последнее время туристов стало так много, что турагент не успевает анализирвать маршруты. Помогите автоматизировать работу турагента, чтобы туристы не теряли времени в ожидании своего маршрута!
Формат входных данных
В первой строке вводится натуральное число n - количество туристических маршрутов в городе (1 <= n <= 10
5). Во следующих n строках вводятся сами маршруты. Каждая строка с маршрутов представляет собой список достопримечательностей (слов), разделенных одним пробелом. Количество достопримечательностей в каждой строке не превышает 10
9. Каждая достопримечательность записана в виде отдельного слова, состоящего только из английских букв и/или цифр.
Последняя строка содержит список достопримечетельностей, которые хочет увитеть турист. Формат этой строки такой же как и в строках выше.
Гарантируется, что самый короткий подходящий маршрут существует и он единственный.
Формат выходных данных
Выведите самый короткий маршрут, включающий все выбранные туристом достопримечательности. Строка с маршрутом должна соответствовать какой-либо одной строке из входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
Park Museum Theater
Museum Castle
Park Embankment
Park Theater Embankment Museum
Park Museum
|
Park Museum Theater
|