Mixing Colours

Frank lives in London and he likes games and maths. Lately he has been playing a simple game on his phone. A row of coloured tokens is given, and on every turn the player merges a pair of adjacent tokens into one token of a certain colour. The turns repeat until a single token is left.

Not every pair of colours can be merged. A set of rules says which combinations are allowed. With the rules

• Blue + Yellow → Green
• Yellow + Red → Orange
• Blue + Orange → Brown

and the row (Blue, Yellow, Red), the game can end with a Brown token after two turns. (Blue, Yellow, Red) → (Blue, Orange) → (Brown)

A rule ignores the order of its two colours. If the rule $s_1 + s_2 \to s_3$ exists, two adjacent tokens merge into one $s_3$ token whether they sit as $(s_1, s_2)$ or as $(s_2, s_1)$.

Frank is now in Valencia for a programming contest. He is waiting for the tram to the university and playing this game to fill time, but the sun shines so bright that he cannot see the screen properly. He has only some certainty about the colour of each token, so he wonders which colour is left at the end of the most likely play according to his estimate. Given his estimate of two colours $A$ and $B$ and the rule $A + B \to C$, the certainty of the obtained colour $C$ is $\mathrm{cer}(C) = \mathrm{cer}(A) \times \mathrm{cer}(B)$.

One play picks a single colour for every token and merges the whole row into one token under the rules. The certainty of that play is the product of the certainties of the picked colours.

The first line contains $R$, the number of rules describing the allowed combinations of colours. ($0 < R \le 100$)

Each of the following $R$ lines contains three strings $s_1$, $s_2$, $s_3$ representing the rule $s_1 + s_2 \to s_3$.

The next line contains the number of test cases $T$.

The first line of each test case contains the length $C$ of the row of tokens. ($0 < C \le 500$)

Each of the next $C$ lines describes one token. It lists pairs of a colour $k$ and its certainty $\mathrm{cer}(k)$, and ends with the word END. ($0 < \mathrm{cer}(k) \le 1.0$)

The certainties of one token always sum to $1.0$. Every colour in a test case has appeared first in the rules.

Print one line for each test case.

If some choice of one colour per token merges the whole row into a single token under the rules, print the colour left at the end of the play whose product of picked certainties is largest. When several colours reach that largest certainty, print the one that comes first in lexicographic (ASCII) order.

For $C = 1$ there is nothing to merge, so the answer is the colour with the largest certainty in that token.

If no play finishes the game, print GAMEOVER.

The first case of the first example has only two tokens. Frank is sure that the second token is Yellow, but the first token could be either Red or Orange. The game can be finished in two ways.

• (Red, Yellow) → (Orange), certainty $0.7$. The rule Yellow + Red → Orange applies with its two colours swapped.
• (Orange, Yellow) → (Yellow), certainty $0.3$.

The first play is more likely, so the final colour is Orange.

The second case has more tokens and estimates. Two possible plays are

• (Blue, Yellow, Yellow, Red) → (Blue, Yellow, Orange) → (Blue, Yellow) → (Green), certainty $0.006$
• (Green, Red, White, Black) → (Green, Pink, Black) → (Green, Red) → (Yellow), certainty $0.036$

The second play is more likely, so the answer is Yellow.

In the third case Frank is sure that the tokens are Blue and Orange. No rule merges those two colours, so the game cannot be finished.

The first case of the second example ends in two plays of equal certainty. In (Red, Red, Yellow), merging the first pair gives Red + Red → Blue and then Blue + Yellow → Green, which leaves Green. Merging the second pair gives Red + Yellow → Purple and then Red + Purple → Cyan, which leaves Cyan. Both plays have certainty $1.0$, so the answer is Cyan, the colour that comes first in lexicographic order.