Задачи
Удовольствие в Бикольском регионе
Удовольствие в Бикольском регионе
Бикольский регион (Регион \textbf{5}) состоит из шести провинций. Это Албай, Северный Камаринес, Южный Камаринес, Сорсогон и острова-провинции Катандуанес и Масбате. В Бикольском регионе расположены города Ирига, Легаспи, Лигао, Масбате, Нага, Сорсогон и Табако.
\includegraphics{https://static.e-olymp.com/content/1a/1a8535855594de709d491ccbb29171e526813eff.jpg}
\textit{\textbf{Рисунок 1}}: Карта Бикольского региона (местоположения приведены только для иллюстрации)
Многие участники не смогли дождаться завершения соревнования, и начали планировать исследование региона. Они начали расспрашивать где находятся определенные города и начали записывать их относительные местоположения.
\InputFile
Входные данные состоят из нескольких тестов. Каждый тест содержит два множества данных. Первое множество описывает относительное расположение первого города ко второму, а второе множество содержит запросы на относительное положение первого города относительно второго. Например
Множество данных 1
Множество данных 2
В приведенном выше примере имеется \textbf{5 }и \textbf{4} записи во множествах данных \textbf{1} и \textbf{2} соответственно.
Множество данных \textbf{1 }состоит из пар городов и их относительного положения. Каждая запись указывает на относительное положение места \textbf{1} к \textbf{2}. Например, запись (Naga City, City of Iriga, Northwest) означает, что город Нага расположен на северо-запад от города Ирига. Множество данных не содержат обратного отношения. Например (City of Iriga, Naga City, Southeast).
Входные данные начинаются двумя целыми числами \textbf{m} и \textbf{n}, задающих количество записей во множестве данных \textbf{1} и \textbf{2} соответственно, причем (\textbf{1 }≤ \textbf{m }≤ \textbf{100}) и (\textbf{1 }≤ \textbf{n }≤ \textbf{50}). Далее следует \textbf{m} записей описания местоположений и\textbf{n }записей запросов.
Данные в записях разделены запятыми и могут содержать смешанные случаи. Возможными относительными положениями являются Север, Юг, Восток, Запад, Северо-Восток, Северо-Запад, Юго-Восток и Юго-Запад. Считается, что каждое относительное положение задает расстояние \textbf{1}. То есть \textbf{1 }на\textbf{ }север, \textbf{1 }на юг, \textbf{1} на восток, \textbf{1 }на запад, \textbf{1 }на север и \textbf{1 }на\textbf{ }восток, \textbf{1} на север и \textbf{1} на запад, \textbf{1} на юг и \textbf{1} на восток, \textbf{1 }на юг и \textbf{1 }на запад соответственно. То есть расстояние от Масбате до Нага такое же как и от Сорсогон до Легаспи.
Между тестами находится пустая строка. За последним тестом следует одно число ноль.
\OutputFile
Для каждого теста выведите относительное местоположение заданных в запросах городов. Вывести "\textbf{Relative location cannot be determined}", если информации для выполнения запроса недостаточно; хотя программа сама должна постараться получить всю необходимую информацию для выполнения запроса.
Входные данные #1
5 4 Naga City,City of Iriga,Northwest Masbate City,Naga City,Southeast Tabaco City,City of Ligao,Northeast Sorsogon City,Legazpi City,Southeast City of Ligao,Legazpi City,West Naga City,City of Iriga City of Iriga, Naga City Sorsogon City, Naga City Sorsogon City, City of Ligao 0
Выходные данные #1
Case 1 Naga City is northwest of City of Iriga City of Iriga is southeast of Naga City Relative location cannot be determined Sorsogon City is southeast of City of Ligao