Hold'em Shark

Problem Description

小Y 养了一群可爱的 Capoo，这些 Capoo 曾经热衷于给算法竞赛出题，然而，它们有一天突然发现，它们需要在两个月内以喵均 $6.25$ 题的 KPI 出完 $25$ 道题。于是它们决定让自己休息一会，先开始一轮 $4$ 只 Capoo 的扑克游戏。 这种扑克游戏以德州扑克为原型，但请仔细阅读下方的题目描述并留意它们与通常规则的区别 扑克牌的点数有 $13$ 种大小，从大到小分别为 A, K, Q, J, T, 9, 8, 7, 6, 5, 4, 3 和 2。其中 A, K, Q, J, T 依次对应 14, 13, 12, 11, 10。此外，扑克牌还有 $4$ 种花色，分别为 红心（Heart），方块（Diamond），梅花（Club）和黑桃（Spade），这四种花色我们利用首字母，分别记为 H, D, C, S 。因此，我们在一局游戏中，一共使用 $13 \times 4 = 52$ 张牌。 一手牌是 $5$ 张牌所构成的集合。每手牌都有一个牌型，而每种牌型也具有一个大小。对于两手牌，如果它们的牌型不同，那么牌型较大的一方始终更大。如果两手牌的牌型相同，为了方便比较，我们将一手牌表达为序列 $(r_1, r_2, r_3, r_4, r_5)$ ，其中 $r_i$ 为第 $i$ 张牌的点数，一手的 $5$ 张牌排列的顺序取决于具体牌型种的描述，随后，我们认为按上述规则表达为序列后较大的一方更大。对于两个序列，我们依次比较每一位的点数，直到某一位它们的点数不同，此时该位点数较大的序列较大，如果比较完最后一位之后仍然相同，则认为两个序列一样大。如果两手牌的牌型和序列均相同，我们认为它们是一样大的。 接下来我们从高到低给出 $10$ 种牌型，如果一手牌满足多种牌型的模式，它属于大小较大的牌型。

• 皇家同花顺：由 T, J, Q, K, A 构成的同花顺
• 同花顺：手牌中包含五张同一花色且点数连续的牌，对应序列满足 $r_1>r_2>r_3>r_4>r_5$ ，请注意：同一花色的 A, 2, 3, 4, 5 构成同花顺，此时 A 的点数被认为比 2 小
• 四条：手牌中包含四张点数相同的牌，对应序列满足 $r_1 = r_2 = r_3 = r_4$
• 葫芦：手牌中包含三张点数相同的牌和另外两张点数相同的牌，对应序列满足 $r_1 = r_2 = r_3$，$r_4 = r_5$
• 同花：手牌中包含五张花色相同的牌，对应序列满足 $r_1>r_2>r_3>r_4>r_5$
• 顺子：手牌中包含五张点数连续的牌，对应序列满足 $r_1>r_2>r_3>r_4>r_5$ ，请注意：A, 2, 3, 4, 5 构成顺子，此时 A 的点数被认为比 2 小
• 三条：手牌中包含三张点数相同的牌，对应序列满足 $r_1 = r_2 = r_3$ ， $r_4 > r_5$
• 两对：手牌中包含两张点数相同的牌以及另外两张点数相同的牌，对应序列满足 $r_1 = r_2 > r_3 = r_4$
• 对子：手牌中包含两张点数相同的牌，对应序列满足 $r_1 = r_2$ ，$r_3 > r_4 > r_5$
• 散牌：不满足以上任一情况的一手牌，对应序列满足 $r_1>r_2>r_3>r_4>r_5$ 在一轮游戏开始时，每只 Capoo 都会被发到 2 张私有牌。由于丰富的算法竞赛命题经验，Capoo 们在仰卧起坐中锻炼出了很高的心理承受能力，因此每只 Capoo 都会等到全部 5 张公共牌都被翻开后进行结算，结算时，每只 Capoo 的手牌大小为它的 2 张私有牌以及桌上的 5 张公共牌所能构成的最大的手牌的大小，手牌大小最大的 Capoo 均为本轮游戏的胜者。 但事情并没有这么简单。小Y 决定给 Capoo 们的游戏增加一些趣味性，他准备对 4 只 Capoo 的共计 8 张私有牌以及桌上的 3 张公共牌（即在翻牌圈（Flop）之后）进行至多 1 次换牌操作，即从这 11 张牌中选择两张牌，并交换它们。 而你的任务则是，根据当前的局势判断，他如何操作可以使得指定位置的 Capoo 胜率最高。

Input

第 $1$ 行为 $1$ 个整数 $T$，满足 $1 \leq T \leq 5$， 为数据的组数。 接下来是 $T$ 组数据，对于每一组数据： 第 $1$ 行为 $3$ 个以空格分隔的字符串，每个字符串的长度均为 $2$，格式为 点数 + 花色，表示桌面上公共牌的大小及花色。其中，第 $i$ 张牌的序号为 $i - 1$。例如，AH KD 3C 代表桌面上的 $3$ 张公共牌分别为 红心A，方块K 以及 梅花3 ，它们的序号依次为 $0$, $1$, $2$。 接下来 $4$ 行，每行 $2$ 个以空格分隔的字符串，每个字符串的长度均为 $2$，格式为 大小 + 花色，第 $i$ 行的两个字符串代表序号为 $i - 2$ 的 Capoo 的两张私有牌的大小和花色。其中，第 $i$ 张牌的序号为 $i - 1$。例如，如果第 $3$ 行为 2S 3S，则说明序号为 $1$ 的 Capoo 的两张私有牌为 黑桃2 和 黑桃3，它们的序号依次为 $0$, $1$。 接下来 $1$ 行，为一个值域是 $[0,3]$ 的整数，表示 小Y 希望最大化胜率的 Capoo 编号。

Output

如果 小Y 使得指定位置的 Capoo 胜率最高不需要进行任何操作，输出一行一个字符串 None。 否则，输出一行 $2$ 个以空格分隔的字符串，每个字符串的长度均为 $2$，格式为 点数 + 花色，描述需要交换的两张牌的点数和花色。请按照字典序升序排序输出需要交换的两张牌。 如果有多种换牌方案都能使得指定的 Capoo 胜率最高，那么优先选择不需要进行任何操作的方案，其次将每种方案按照字典序升序对需要交换的两张牌排序并拼接，然后取字典序最小的方案。

Sample Input

1
8H QS 8C
4D 9D
2C AH
QC QH
7S AD
3

Sample Output

7S QC

Source

2024“钉耙编程”中国大学生算法设计超级联赛（7）