P12956 [GCJ Farewell Round #3] Game Sort: Part 1

**注意**：问题 **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 赢得游戏，或者判断这是否不可能吗？

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

对于每个测试用例，输出一行 `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}$。如果有多种解，输出任意一种即可。

**样例解释** 在样例 #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 完成