两名玩家正在玩在线纸牌游戏。该游戏使用 32 张牌进行。每张牌都有一个花色和一个等级。有四种花色:梅花、方块、红心和黑桃。我们将分别用字符“C”、“D”、“H”和“S”对它们进行编码。共有 8 个等级,按升序排列:“2”、“3”、“4”、“5”、“6”、“7”、“8”、“9”。
每张牌都由两个字母表示:牌号和花色。例如,红心 8 表示为 8H。
游戏开始时,选择一套花色作为王牌花色。
在每一轮中,玩家的行动如下:第一个玩家将他的一张牌放在桌子上,第二个玩家必须用他们的一张牌击败这张牌。之后,两张牌都会被移至弃牌堆。
如果两张牌的花色相同且第一张牌的点数高于第二张牌,则一张牌可以击败另一张牌。比如8S可以打败4S。此外,王牌可以击败任何非王牌,无论牌的等级如何,例如,如果王牌花色是梅花(“C”),则 3C 可以击败 9D。请注意,王牌只能被更高等级的王牌击败。
游戏中进行了 $$$n$$$ 轮,因此弃牌堆现在包含 $$$2n$$$ 卡。您想要重建游戏中进行的回合,但弃牌堆中的牌被洗乱了。找出游戏中可能已经玩过的任何可能的 $$$n$$$ 轮序列。
输入
第一行包含整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
测试用例的第一行包含整数 $$$n$$$ ($$$1\le n\le 16$$$)。
测试用例的第二行包含一个字符,即王牌花色。它是“CDHS”之一。
测试用例的第三行包含 $$$2n$$$ 卡的描述。每张牌都由一个双字符的字符串描述,第一个字符是牌的点数,即“23456789”之一,第二个字符是牌的花色,即“CDHS”之一。所有卡都不同。
输出
对于每个测试用例,打印其答案:
- 打印 $$$n$$$ 行。在每一行中,以与输入中相同的格式打印两张牌的描述:第一个玩家打出的第一张牌,然后是第二个玩家用来击败它的牌。
- 如果没有解决方案,则打印一行“IMPOSSIBLE”。
如果有多个解决方案,请打印其中任何一个。
示例
输入 #1
8 3 S 3C 9S 4C 6D 3S 7S 2 C 3S 5D 9S 6H 1 H 6C 5D 1 S 7S 3S 1 H 9S 9H 1 S 9S 9H 1 C 9D 8H 2 C 9C 9S 6H 8C
输出 #1
3C 4C 6D 9S 3S 7S IMPOSSIBLE IMPOSSIBLE 3S 7S 9S 9H 9H 9S IMPOSSIBLE 6H 9C 9S 8C