Задоволення у Бікольському регіоні
Задоволення у Бікольському регіоні
Бікольський регіон (Регіон 5) складається з шести провінцій. Це Албай, Північний Камаринес, Південний Камаринес, Сорсогон та острови-провінції Катандуанес та Масбате. У Бікольському регіоні розміщені міста Іріга, Легаспі, Лігао, Масбате, Нага, Сорсогон та Табако.
Рисунок 1: Карта Бікольського регіону (місцезнаходження наведені лише для ілюстрації)
Багато з учасників не змогли дочекатись завершення змагань, і почали планувати дослідження регіону. Вони почали розпитувати де знаходяться певні міста і почали записувати їх відносне місцезнаходження.
Вхідні дані
Вхідні дані складаються з декількох тестів. Кожен тест містить дві множини даних. Перша множина описує відносне розміщення першого міста до другого, а друга множина містить запити про відносне положення першого міста відносно другого. Наприклад
Множина даних 1
Множина даних 2
У наведеному вище прикладі є 5 і4 записи у множинах даних 1 та 2 відповідно.
Множина даних 1 складається з пар міст та їх відносного положення. Кажен запис вказує на відносне положення города 1 до 2. Наприклад, запис (Naga City, City of Iriga, Northwest) означає, що місто Нага розміщено на північний захід від міста Іріга. Множини даних не містять зворотного відношення. Наприклад (City of Iriga, Naga City, Southeast).
Вхідні дані починаються двома цілими числами m та n, які задають кількість записів у множинах даних 1 та 2 відповідно, причому (1 ≤ m ≤ 100) та (1 ≤ n ≤ 50). Далі йде m записів опису місцезнаходження та n записів запитів.
Дані у записах відокремлено комами і можуть містити змішані випадки. Можливими відносними положеннями є Північ, Південь, Схід, Захід, Північний Схід, Північний Захід, Південний Схід та Південний Захід. Вважається, що кожне відносне положення задає відстань 1. Тобто 1 на північ, 1 на південь, 1 на схід, 1 на захід, 1 на північ та 1 насхід, 1 на північ і 1 на захід, 1 на південь і 1 на схід, 1 на південь і 1 на захід відповідно. Тобто відстань від от Масбате до Нага така ж як і від Сорсогон до Легаспі.
Між тестами знаходиться порожній рядок. За останнім тестом йде одне число нуль.
Вихідні дані
Для кожного тесту виведіть відносне місцезнаходження заданих у запитах міст. Вивести "Relative location cannot be determined", якщо інформації для виконання запиту недостатньо; хоча програма сама повинна постаратись отримати усю необхідну інформацію для виконання запиту.
Приклад
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
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