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}$ 和一个字符串 $\mathbf{S}$，分别表示分割数量和待分割的字符串。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 POSSIBLE（如果 Amir 可以赢得游戏）或 IMPOSSIBLE（如果他不能）。如果可以赢得游戏，则额外输出一行，包含 $t_1 t_2 \ldots t_p$，其中 $t_i$ 是你为 Amir 找到的获胜分割的第 $i$ 部分。如果有多种解，可以输出其中任意一种。

3
3 CODEJAM
2 ABABABABAAAA
3 AABBCDEEFGHIJJKLMNOPQRRSTUVWXYZZ

Case #1: POSSIBLE
C O DEJAM
Case #2: POSSIBLE
ABABABABA AAA
Case #3: IMPOSSIBLE

Hint

样例解释

在样例 #1 中，Badari 无法将 $\text{DEJAM}$ 重新排列为字典序大于 $\text{O}$ 的字符串，因此 Amir 确保了胜利。

在样例 #2 中，$\text{AAA}$ 的字典序必然小于任何包含超过 3 个字母的字符串的重排结果，因此 Amir 也获胜。

在样例 #3 中，所有可能的分割方式都会使得部分列表已经按字典序排列，因此 Amir 无法获胜。

限制

• $1 \leq \mathbf{T} \leq 100$。
• $\mathbf{S}$ 的每个字符均为大写字母 A 到 Z。

测试集 1（8 分，可见评测结果）

• $2 \leq \mathbf{P} \leq 3$。
• $\mathbf{P} \leq \mathbf{S} \text{ 的长度} \leq 100$。

测试集 2（20 分，隐藏评测结果）

• $2 \leq \mathbf{P} \leq 100$。
• $\mathbf{P} \leq \mathbf{S} \text{ 的长度} \leq 10^5$。

翻译由 DeepSeek V3 完成