29797번 - 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} = \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 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}, \dots, \mathbf{S_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 POSSIBLE if Badari can win the game, or IMPOSSIBLE if she cannot. If she can win the game, output a second line containing $t_1,円 t_2 ,円\dots,円 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.

제한

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

Test Set 1 (4점)

• 2ドル \le \mathbf{P} \le 3$.
• 1ドル \le $ the length of $\mathbf{S_i} \le 8,ドル for all $i$.

Test Set 2 (9점)

• 2ドル \le \mathbf{P} \le 100$.
• 1ドル \le $ the length of $\mathbf{S_i} \le 100,ドル for all $i$.

힌트

In Sample Case #1, Badari could also win in 5ドル$ other ways. Two of them are [CO, JED, MA] and [CO, EJD, 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.