Description

经过无数个不眠之夜，你终于教会了机械臂做出石头剪刀布游戏所需的手势。现在你只需要编写程序，让它在即将到来的机器人锦标赛中参赛！

在本次锦标赛中，每个机器人都使用一个程序，该程序是一系列动作，每个动作必须是以下三者之一：R（代表“石头”）、P（代表“布”）或 S（代表“剪刀”）。布胜石头，输给剪刀；石头胜剪刀，输给布；剪刀胜布，输给石头。

当两个机器人进行对决时，先出制胜动作的机器人获胜。比赛开始时，每个机器人出程序中的第一个动作。如果两个动作不同，其中一个动作会击败另一个动作，从而有一个机器人获胜。如果两个动作相同，则每个机器人出程序中的下一个动作，依此类推。

每当一个机器人走到程序末尾需要下一个动作时，它会回到程序的开头。例如，程序为 RSSP 的机器人，第五步将是 R。如果一场比赛持续超过一个 googol（$10^{100}$）步，裁判会抛硬币决定胜者。

一场比赛结束后，获胜的机器人会重置，因此它不会记得这场比赛。在下一场比赛中，它会从程序的第一个动作开始，依此类推。

锦标赛共进行 $K$ 轮，采用单败淘汰“对阵表”结构。共有 $N=2^K$ 个机器人，编号为 $0$ 到 $N-1$。第一轮中，机器人 $0$ 对阵机器人 $1$，机器人 $2$ 对阵机器人 $3$，以此类推，直到机器人 $N-2$ 和 $N-1$。这些比赛的失败者被淘汰。第二轮中，$0-1$ 比赛的胜者对阵 $2-3$ 比赛的胜者，依此类推。到第 $K$ 轮时，只剩下一场比赛，决定锦标赛的总冠军。

其他参赛者都非常自信，已经在网上公开了他们机器人的程序。然而，机器人编号尚未分配，因此没人提前知道对手是谁。已知所有其他机器人的程序，你能否编写一个程序，无论机器人编号如何分配，都能保证你赢得锦标赛？

Input Format

输入的第一行给出测试用例数 $T$；接下来是 $T$ 组测试数据。每组测试数据的第一行包含一个整数 $A$，表示锦标赛中对手（其他机器人）的数量。接下来有 $A$ 行，第 $i$ 行包含一个字符串 $C_i$，表示第 $i$ 个对手机器人的程序，由大写字母组成。

Output Format

对于每个测试用例，输出一行 Case #x: y。如果存在一个长度在 $1$ 到 $500$ 之间的字符串，能保证你赢得锦标赛，则 $y$ 应为表示该程序的大写字母字符串。否则，$y$ 应为大写字母 IMPOSSIBLE。

3
1
RS
3
R
P
S
7
RS
RS
RS
RS
RS
RS
RS

Case #1: RSRSRSP
Case #2: IMPOSSIBLE
Case #3: P

Hint

样例说明

注意：虽然每个样例中所有对手的程序长度相同，但实际情况并非如此。一个测试用例中的对手程序长度可能不同。

在样例 1 中，只有一个对手，程序为 RS。我们的答案在一段时间内与对手的动作相同，对手的程序循环多次。当对手开始第四次循环时，我们用 P 击败了它。其他有效答案还包括 P、RR 和 R。

在样例 2 中，有三个对手，程序分别为 R、P 和 S。你需要自己思考为什么这个用例的答案是 IMPOSSIBLE！

在样例 3 中，所有七个对手都使用相同的程序。例如，使用程序 P 可以保证你获胜。记住，每次对阵新对手时，每个机器人都会从程序的第一个动作开始。

数据范围

• $1 \leqslant T \leqslant 100$。
• 每个 $\mathbf{C}_i$ 的每个字符均为大写字母 $\mathbf{R}$、$\mathbf{P}$ 或 $\mathbf{S}$。
• $\mathbf{A}=2^{\mathbf{K}}-1$，其中整数 $\mathbf{K} \geqslant 1$。

测试点 1（10 分，可见）

• $1 \leqslant \mathbf{A} \leqslant 7$。
• 每个 $\mathbf{C}_i$ 的长度为 $1$ 到 $5$。

测试点 2（18 分，隐藏）

• $1 \leqslant \mathbf{A} \leqslant 255$。
• 每个 $\mathbf{C}_i$ 的长度为 $1$ 到 $500$。

由 ChatGPT 4.1 翻译