게임 정렬: Part 1

참고: 문제 Game Sort: Part 1과 Game Sort: Part 2의 본문은 마지막 문단을 제외하면 같다. 그 밖의 내용으로는 두 문제를 각각 독립적으로 풀 수 있다.

Amir와 Badari가 정렬 게임을 한다. 심판이 공정하게 정한 문자열 $\mathbf{S}$와 정수 $\mathbf{P}$로 게임이 시작된다. Amir는 $\mathbf{S}$를 정확히 $\mathbf{P}$개의 연속된 비어 있지 않은 부분 문자열로 나눠야 한다. 예를 들어 $\mathbf{S}$가 CODEJAM이고 $\mathbf{P} = 3$이면, Amir는 [COD, EJA, M] 또는 [CO, D, EJAM]으로 나눌 수 있다. 하지만 [COD, EJAM], [COD, JA, M], [EJA, COD, M], [CODE, EJA, M]으로는 나눌 수 없다.

그다음 Badari는 각 부분의 글자를 재배열해서, 부분들을 나열했을 때 사전순으로 정렬되도록 해야 한다(같은 문자열은 허용). 성공하면 Badari가 이기고, 그렇지 못하면 Amir가 이긴다. Amir가 만든 분할이 주어졌을 때, Badari가 이기도록 도울 수 있는지 판단하라. 이길 수 없다면 불가능하다고 답하라.

첫 줄에 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 Amir가 만든 부분의 개수 $\mathbf{P}$가 하나의 정수로 주어진다. 둘째 줄에는 순서대로 $\mathbf{P}$개의 문자열 $\mathbf{S\_1}, \mathbf{S\_2}, \dots, \mathbf{S\_P}$가 주어진다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 Badari가 이길 수 있으면 POSSIBLE, 이길 수 없으면 IMPOSSIBLE이다. 이길 수 있다면 두 번째 줄에 $t\_1\, t\_2\, \dots\, t\_{\mathbf{P}}$를 출력한다. 여기서 $t\_i$는 $\mathbf{S\_i}$의 글자를 재배열한 문자열이고, 모든 $i$에 대해 $t\_i$는 $t\_{i+1}$보다 사전순으로 앞서거나 같아야 한다. 답이 여러 개이면 그중 아무거나 출력해도 된다.

$1 \le \mathbf{T} \le 100$.

모든 $i$에 대해 $\mathbf{S\_i}$의 각 문자는 영문 대문자 A부터 Z까지 중 하나이다.

예제 #1에서 Badari는 다른 방법 5가지로도 이길 수 있다. 그중 두 가지는 [CO, JED, MA]와 [CO, EJD, MA]이다.

예제 #2에서 Badari는 Amir가 준 부분을 그대로 두기만 해도 이긴다. 다른 방법도 가능하다.

예제 #3에서 Amir는 Badari에게 이길 선택지를 남기지 않아 자신의 승리를 보장했다.