Смешивание цветов
Фрэнк живет в Лондоне, и он очень любит игры и математику. В последнее время он играет в игру на своем мобильном телефоне. Она довольно проста: имеется последовательность цветных фигурок и за каждый ход игрок должен объединить пару соседних фигур для получения новой определенного цвета. Этот процесс повторяется до тех пор пока вся последовательность не приведет к единственной конечной фигурке. Проблема в том, что не каждая пара цветов может объединяться. Существует набор правил, описывающий разрешенные комбинации. Например, пусть заданы следующие правила
blue + yellow → green
yellow + red → orange
blue + orange → brown
и последовательность (blue, yellow, red). Игра может закончиться коричневой фигуркой через два шага: (blue, yellow, red) → (blue, orange) → (brown).
Сейчас Фрэнк в Валенсии на знаменитом конкурсе по программированию, он как раз ждет трамвая, чтобы добраться в университет. Между тем, он играет в эту игру, чтобы скоротать время. Солнце светит так ярко, что он не может должным образом видеть экран своего телефона. У Фрэнка имеется некоторая определенность в отношении возможного цвета каждой фигурки, и он задается вопросом, какой будет результирующий цвет после наиболее вероятного сценария игры в результате оценки входной последовательности.
Имеется оценка Фрэнком двух цветов A и B, и комбинация A + B → C, вероятность получить цвет 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. Не существует правила, по которому их можно скомбинировать, поэтому игра не имеет решения.