最后一次猜测 - 题目

如果你在去年年底花过时间在社交媒体上，你可能对猜词游戏 Wordle 很熟悉。在这个游戏中，你需要用最多六次猜测机会找到一个五个字母的英文单词。每次猜测后，该猜测中的字母会被标记为绿色、黄色或黑色，以提供关于隐藏单词的信息：

绿色表示该字母在隐藏单词中且位置正确。
黄色表示该字母在隐藏单词中，但位置错误。
黑色表示该字母在隐藏单词中没有更多出现。
如果一个字母在猜测的单词中出现多次，首先放置该字母所有的绿色标记。然后，从左到右，为隐藏单词中剩余的该字母的每次出现放置黄色标记。最后，为猜测单词中该字母多余的出现放置黑色标记。参见图 L.1 示例。

图 L.1：样例输入 1 的说明，其中 “upper” 是唯一有效的最后一次猜测。

在本题中，我们考虑 Wordle 的一个变体，你需要用最多 $g$ 次猜测找到一个长度为 $\ell$ 的隐藏单词。此外，不要求隐藏单词或任何猜测是任何语言的单词；任何由小写英文字母组成的字符串都可以。

在你当前进行的这一局变体游戏中，你已经用掉了除最后一次机会外的所有猜测，现在你需要利用最后一次猜测找到隐藏单词。请根据你拥有的信息，找出任何可能是该隐藏单词的词。

输入包含：

一行包含两个整数 $g$ 和 $\ell$ ($2 \le g \le 500, 1 \le \ell \le 500$)，分别为游戏中允许的最大猜测次数和单词长度。
$g - 1$ 行，每行包含两个长度为 $\ell$ 的字符串 $s$ 和 $t$，其中 $s$ 是目前为止的一次猜测，$t$ 是根据上述规则给出的该猜测的颜色反馈。字符串 $s$ 由小写英文字母 (a-z) 组成，字符串 $t$ 由大写字母 ‘G’、‘Y’ 和 ‘B’ 组成，分别表示绿色、黄色和黑色。

保证输入描述了 Wordle 游戏在最后一次猜测前的有效状态，并且存在一个由小写英文字母组成的长度为 $\ell$ 的有效隐藏单词解。

输出一个有效的最后一次猜测，使你有机会获胜。

如果有多个有效解，你可以输出其中任意一个。

4 5
reply YYGBB
refer BBBGG
puppy YYGBB

upper

2 12
aabbccddeeff GGGYGBYYYBBB

aabdcbegdhij

QOJ.ac