Задоволення у Бікольському регіоні#6246
Бікольський регіон (Регіон 5) складається з шести провінцій: Албай, Північний Камаринес, Південний Камаринес, Сорсогон та острівні провінції Катандуанес і Масбате. У регіоні знаходяться міста: Іріга, Легаспі, Лігао, Масбате, Нага, Сорсогон і Табако.
Рисунок 1: Карта Бікольського регіону (місця показано лише для ілюстрації)
Після завершення змагання багато учасників захотіли дослідити регіон. Вони почали цікавитися розташуванням міст і записувати відносні позиції між ними.
Вхідні дані містять кілька тестових випадків.
Кожен тестовий випадок складається з двох наборів даних: - Перший містить інформацію про відносне розташування одного міста відносно іншого. - Другий — список запитів щодо відносного розташування одного міста до іншого.
На початку кожного тесту два цілі числа і — кількість записів у наборах даних 1 та 2 відповідно, де 1 \leq m \leq 100 і 1 \leq n \leq 50.
Далі йдуть рядків з інформацією про відносне розташування у форматі:
city_name_1, city_name_2, relative_position
Потім рядків із запитами:
city_name_1, city_name_2
Можливі значення напрямків: north, south, east, west, northeast, northwest, southeast, southwest. Дані розділені комами, імена міст можуть бути у змішаному регістрі. Вважається, що кожен базовий напрямок має одиничну довжину: "north" — це на північ, "northeast" — це на північ і на схід тощо. Зворотних відносин у даних не міститься.
Між тестами — порожній рядок. Після останнього тесту — один нуль.
Для кожного тесту виведіть відповідь для кожного запиту. Якщо інформації недостатньо — виведіть "Relative location cannot be determined". Використовуйте всю отриману інформацію для відповіді.
Приклад 1