29801번 - 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} = \vphantom{}$CODEJAM was the chosen string and $\mathbf{P} = 3,ドル Amir could split it up as [COD, EJA, M] or as [CO, D, EJAM], but not as [COD, EJAM], [COD, JA, M], [EJA, COD, M], nor as [CODE, EJA, 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,円 \dots,円 t_{\mathbf{P}}$ where $t_i$ is a the $i$-th part of the winning partition you found for Amir. If there are multiple solutions, you may output any one of them.

제한

• 1ドル \le \mathbf{T} \le 100$.
• Each character of $\mathbf{S}$ is an English uppercase letter A through Z.

Test Set 1 (8점)

• 2ドル \le \mathbf{P} \le 3$.
• $\mathbf{P} \le $ the length of $\mathbf{S} \le 100$.

Test Set 2 (20점)

• 2ドル \le \mathbf{P} \le 100$.
• $\mathbf{P} \le $ the length of $\mathbf{S} \le 10^5$.

힌트

In Sample Case #1, there is no way for Badari to rearrange DEJAM to be lexicographically after O, so Amir guaranteed a win.

In Sample Case #2, 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.