P12960 [GCJ Farewell Round #3] Game Sort: Part 2

Note: The main parts of the statements of the problems "Game Sort: Part 1" and "Game Sort: Part 2" are identical, except for the last paragraph. The problems can otherwise be solved independently. Amir and Badari are playing a sorting game. The game starts with a string $\mathbf{S}$ and an integer $\mathbf{P}$ being chosen by an impartial judge. Then, Amir has to split $\mathbf{S}$ into exactly $\mathbf{P}$ contiguous non-empty parts (substrings). For example, if $\mathbf{S} = \text{CODEJAM}$ was the chosen string and $\mathbf{P} = 3$, Amir could split it up as $[\text{COD}, \text{EJA}, \text{M}]$ or as $[\text{CO}, \text{D}, \text{EJAM}]$, but not as $[\text{COD}, \text{EJAM}]$, $[\text{COD}, \text{JA}, \text{M}]$, $[\text{EJA}, \text{COD}, \text{M}]$, nor as $[\text{CODE}, \text{EJA}, \text{M}]$. Then, Badari must rearrange the letters within each part to make the list of parts be sorted in non-decreasing lexicographical order. If she can, then she wins. Otherwise, Amir wins. Given the initial string and number of parts, can you help Amir win the game by choosing his parts in a way Badari cannot win herself? If not, say that it is not possible.

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ lines follow, each describing a single test case containing an integer $\mathbf{P}$ and a string $\mathbf{S}$, the number of parts and string to be partitioned, respectively.

For each test case, output one line containing `Case #x: y`, where $x$ is the test case number (starting from 1) and $y$ is either `POSSIBLE` if Amir can win the game, or `IMPOSSIBLE` if he cannot. If he can win the game, output a second line containing $t_1 t_2 \ldots t_p$ where $t_i$ is the $i$-th part of the winning partition you found for Amir. If there are multiple solutions, you may output any one of them.

**Sample Explanation** In Sample Case #1, there is no way for Badari to rearrange $\text{DEJAM}$ to be lexicographically after $\text{O}$, so Amir guaranteed a win. In Sample Case #2, $\text{AAA}$ is guaranteed to be earlier than any rearrangement of a string containing more than 3 letters, so Amir also wins. In Sample Case #3, all possible partitions result in a list of parts that is already sorted in lexicographical order, so Amir cannot possibly win. **Limits** $1 \leq \mathbf{T} \leq 100$. Each character of $\mathbf{S}$ is an English uppercase letter A through Z. **Test Set 1 (8 Pts, Visible Verdict)** - $2 \leq \mathbf{P} \leq 3$. - $\mathbf{P} \leq \text{the length of } \mathbf{S} \leq 100$. **Test Set 2 (20 Pts, Hidden Verdict)** - $2 \leq \mathbf{P} \leq 100$. - $\mathbf{P} \leq \text{the length of } \mathbf{S} \leq 10^5$.