[HAOI2008] 玩具取名

题目描述

有四种玩具，名字分别为 W、I、N、G。每一种玩具都可以按照若干条规则变成两个玩具。例如规则 II 表示一个 W 可以变成两个 I。

现在给出四种玩具各自的变换规则，以及一串变换后的玩具名字。请判断这串名字最初可能是哪一种玩具。一个区间能由某种玩具变成，当且仅当它可以按该玩具的一条规则分成左右两段，并且左右两段分别能由规则中的两个玩具变成。

输入格式

第一行四个整数 $n_W,n_I,n_N,n_G$，分别表示 W、I、N、G 的规则数量。

接下来依次输入 W、I、N、G 的全部规则，每条规则是一行两个大写字母。

最后一行输入变换后的玩具名字。

输出格式

按照 WING 的顺序输出所有可能的初始玩具名字，不加空格。

如果没有任何一种玩具符合要求，输出 The name is wrong!。

样例输入

1 1 1 1
II
WW
WW
IG
IIII

样例输出

IN

数据范围与约定

变换后的名字长度 $L\le 200$，每一种玩具的规则数不超过 $16$。输入字符只会是 W、I、N、G。

题目来源：洛谷 P4290