背景

译自 Northwestern Europe Regional Contest (NWERC) 2022 Problem L。

原题许可协议为 CC BY-SA。

题目描述

如果你去年年底在社交媒体上花过一些时间，你大概熟悉找词游戏 Wordle。在这个游戏中，你需要在最多六次猜测内找出一个五个字母的英语单词。每次猜测后，猜测中的字母会被标成绿色、黄色或黑色，以提供关于隐藏单词的信息：

• 绿色表示该字母在隐藏单词中，并且出现在相同位置。
• 黄色表示该字母在隐藏单词中，但出现在不同位置。
• 黑色表示该字母在隐藏单词中没有更多出现次数。
• 如果某个字母在猜测单词中出现多次，首先会为这个字母放置所有绿色标记。然后，从猜测单词的左到右，为隐藏单词中剩余的该字母出现次数放置黄色标记。最后，猜测单词中多余的该字母会被标记为黑色。下图给出了一个例子。

:::align{center}

:::

图：样例输入 1 的示意图，其中 upper 是唯一合法的最后一猜。

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

在你当前进行的这局变体游戏中，你已经用完了除最后一次以外的所有猜测，现在需要用最后一猜找出隐藏单词。请根据你已获得的信息，找出任意一个可能是隐藏单词的单词。

输入格式

输入包含：

• 一行两个整数 $g$ 和 $\ell$（$2 \leq g \leq 500$，$1 \leq \ell \leq 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

提示

【数据规模与约定】

对于所有数据，满足 $2 \leq g \leq 500$，$1 \leq \ell \leq 500$；猜测串由小写英文字母构成，颜色串由 G、Y、B 构成；保证存在合法最后一猜。