Description

注意：问题 Game Sort: Part 1 和 Game Sort: Part 2 的题目描述主要部分相同，仅最后一段不同。这两个问题可以独立解决。

Amir 和 Badari 正在玩一个排序游戏。游戏开始时，一位公正的裁判会选择一个字符串 $\mathbf{S}$ 和一个整数 $\mathbf{P}$。然后，Amir 需要将 $\mathbf{S}$ 分割成恰好 $\mathbf{P}$ 个连续的非空部分（子字符串）。例如，如果选择的字符串是 $\mathbf{S} = \text{CODEJAM}$ 且 $\mathbf{P} = 3$，Amir 可以将其分割为 $[\text{COD}, \text{EJA}, \text{M}]$ 或 $[\text{CO}, \text{D}, \text{EJAM}]$，但不能分割为 $[\text{COD}, \text{EJAM}]$、$[\text{COD}, \text{JA}, \text{M}]$、$[\text{EJA}, \text{COD}, \text{M}]$ 或 $[\text{CODE}, \text{EJA}, \text{M}]$。

接着，Badari 必须对每个部分的字母重新排列，使得这些部分按字典序非递减的顺序排列。如果她能完成，则她获胜；否则，Amir 获胜。

给定 Amir 的分割方案，你能帮助 Badari 赢得游戏，或者判断这是否不可能吗？

Input Format

输入的第一行包含测试用例的数量 $\mathbf{T}$。接下来是 $\mathbf{T}$ 个测试用例。每个测试用例包含两行：第一行是一个整数 $\mathbf{P}$，表示 Amir 分割的部分数量；第二行包含 $\mathbf{P}$ 个字符串 $\mathbf{S}_1, \mathbf{S}_2, \ldots, \mathbf{S}_\mathbf{P}$，按顺序表示分割后的部分。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 POSSIBLE（如果 Badari 可以获胜）或 IMPOSSIBLE（如果她不能）。如果她可以获胜，则额外输出一行，包含 $t_1 t_2 \ldots t_\mathbf{P}$，其中 $t_i$ 是 $\mathbf{S}_i$ 的字母重新排列后的结果，且对于所有 $i$，$t_i$ 的字典序不大于 $t_{i+1}$。如果有多种解，输出任意一种即可。

3
3
CO DEJ AM
3
CODE JA M
2
ABABABAB AAA

Case #1: POSSIBLE
CO DEJ MA
Case #2: POSSIBLE
CODE JA M
Case #3: IMPOSSIBLE

Hint

样例解释

在样例 #1 中，Badari 还可以通过其他 5 种方式获胜，其中两种是 $[\text{CO}, \text{JED}, \text{MA}]$ 和 $[\text{CO}, \text{EJD}, \text{MA}]$。

在样例 #2 中，Badari 可以直接保留 Amir 给出的分割方案获胜，但其他方式也是可行的。

在样例 #3 中，Amir 确保了 Badari 无法获胜。

限制条件

• $1 \leq \mathbf{T} \leq 100$。
• 对于所有 $i$，$\mathbf{S}_i$ 的每个字符均为大写字母 A 到 Z。

测试集 1（4 分，可见判定）

• $2 \leq \mathbf{P} \leq 3$。
• 对于所有 $i$，$1 \leq \mathbf{S}_i \text{ 的长度} \leq 8$。

测试集 2（9 分，隐藏判定）

• $2 \leq \mathbf{P} \leq 100$。
• 对于所有 $i$，$1 \leq \mathbf{S}_i \text{ 的长度} \leq 100$。

翻译由 DeepSeek V3 完成