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

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 partition Amir made, can you help Badari win the game, or say that it is not possible?

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each test case consists of two lines. The first line of a test case contains a single integer $\mathbf{P}$, the number of parts Amir made. The second line contains $\mathbf{P}$ strings $\mathbf{S}_1, \mathbf{S}_2, \ldots, \mathbf{S}_\mathbf{P}$, representing the $\mathbf{P}$ parts, in order.

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 $\text{POSSIBLE}$ if Badari can win the game, or $\text{IMPOSSIBLE}$ if she cannot. If she can win the game, output a second line containing $t_1 t_2 \ldots t_\mathbf{P}$ where $t_i$ is a rearrangement of the letters of $\mathbf{S}_i$, and $t_i$ is lexicographically earlier than or equal to $t_{i+1}$, for all $i$. If there are multiple solutions, you may output any one of them.

**Sample Explanation** In Sample Case #1, Badari could also win in 5 other ways. Two of them are $[\text{CO}, \text{JED}, \text{MA}]$ and $[\text{CO}, \text{EJD}, \text{MA}]$. In Sample Case #2, Badari can win simply by leaving all parts as Amir gave it to her, but other ways are also possible. In Sample Case #3 Amir has guaranteed a win for himself leaving Badari no winning option. **Limits** $1 \leq \mathbf{T} \leq 100$. Each character of $\mathbf{S}_i$ is an English uppercase letter A through Z, for all $i$. **Test Set 1 (4 Pts, Visible Verdict)** - $2 \leq \mathbf{P} \leq 3$. - $1 \leq \text{the length of } \mathbf{S}_i \leq 8$, for all $i$. **Test Set 2 (9 Pts, Hidden Verdict)** - $2 \leq \mathbf{P} \leq 100$. - $1 \leq \text{the length of } \mathbf{S}_i \leq 100$, for all $i$.