Змішування кольорів
Френк живе в Лондоні й дуже захоплюється іграми та математикою. Нещодавно він почав грати в гру на своєму мобільному телефоні. Гра досить проста: є послідовність кольорових фігурок, і на кожному ході гравець повинен об'єднати пару сусідніх фігурок, щоб отримати нову фігурку певного кольору. Цей процес повторюється, поки вся послідовність не зведеться до однієї кінцевої фігурки. Проблема в тому, що не всі пари кольорів можуть об'єднуватися. Існує набір правил, що описують дозволені комбінації. Наприклад, розглянемо такі правила:
blue + yellow → green
yellow + red → orange
blue + orange → brown
і послідовність (blue, yellow, red). Гра може завершитися коричневою фігуркою за два кроки: (blue, yellow, red) → (blue, orange) → (brown).
Зараз Френк перебуває у Валенсії на відомому конкурсі з програмування, чекаючи трамвая, щоб дістатися до університету. Тим часом, він грає в цю гру, щоб скоротати час. Сонце світить так яскраво, що він не може чітко бачити екран свого телефону. Френк має певну впевненість щодо можливого кольору кожної фігурки і хоче дізнатися, яким буде кінцевий колір після найбільш ймовірного сценарію гри, оцінюючи вхідну послідовність.
Френк оцінює ймовірність отримання кольору C з комбінації кольорів A і B за правилом A + B → C як cer(C) = cer(A) · cer(B).
Вхідні дані
Перший рядок містить кількість правил r (0 < r ≤ 100), що визначають можливі комбінації кольорів. Кожен з наступних r рядків містить три рядки s_1, s_2, s_3, що описують комбінацію s_1 + s_2 → s_3. Наступний рядок задає кількість тестів t. Для кожного тесту задається довжина c (0 < c ≤ 500) вхідної послідовності фігурок. Кожен з наступних c рядків описує фігурку, містячи список пар (k, cer(k)), що задають колір k і відповідну ймовірність (0 < cer(k) ≤ 1.0). Список завершується словом END. Сума ймовірностей для кожної фігурки завжди дорівнює 1.0. Кожен колір у тестах спочатку зустрічається в правилах, що описують гру.
Вихідні дані
Для кожного тесту виведіть колір, з яким найбільш ймовірно закінчити гру. Якщо завершити гру неможливо, виведіть GAMEOVER.
Пояснення до прикладів
Перший тест
У першому тесті всього дві фігурки. Френк впевнений, що друга фігурка Yellow, але першою може бути Red або Orange. Є два можливих рішення гри:
1. (Red; Yellow) → (Orange) :
cer(Orange) = 0.7
2. (Orange; Yellow) → (Yellow) :
cer(Yellow) = 0.3
За оцінками Френка більш ймовірно закінчення 1, тому фінальний колір Orange.
Другий тест
У другому тесті є кілька фігурок і оцінок. Два можливих рішення:
1. (Blue,Yellow,Yellow,Red) → (Blue,Yellow,Orange) → (Blue,Yellow) → (Green)
cer(Green) = 0.006
2. (Green,Red,White,Black) → (Green,Pink,Black) → (Green,Red) → (Yellow)
cer(Yellow) = 0.036
За оцінками Френка більш ймовірно закінчення 2, тому фінальний колір Yellow.
Третій тест
Френк впевнений, що у нього є дві фігурки Blue і Orange. Не існує правила, за яким їх можна скомбінувати, тому гра не має рішення.