P4290 [HAOI2008] Toy Naming

Someone has a set of toys and wants to give them names. First, he chooses any one letter from `W, I, N, G` as the base name of a toy. Then, according to his preference, he can replace any letter in the current name with any allowed pair of letters from `W, I, N, G`, so that the name can grow very long. Now, given a very long name, he wants you to guess which initial letters it could have been derived from.

The first line contains four integers $W, I, N, G$, indicating how many different pairs of letters each letter can be replaced by. The next $W$ lines each contain two letters, indicating that `W` can be replaced by these two letters. The next $I$ lines each contain two letters, indicating that `I` can be replaced by these two letters. The next $N$ lines each contain two letters, indicating that `N` can be replaced by these two letters. The next $G$ lines each contain two letters, indicating that `G$ can be replaced by these two letters. The last line contains a string of length $L$, representing the toy’s name.

Output a single line string listing the letters from which the given name could have been derived (in the order `W, I, N, G`). If the given name cannot be derived from any letter, output `The name is wrong!`.

Constraints - $30\%$ of the testdata satisfies $L \leq 20$, $W, I, N, G \leq 6$. - $100\%$ of the testdata satisfies $L \leq 200$, $W, I, N, G \leq 16$. Translated by ChatGPT 5