격자 탈출

$R$행 $C$열의 직사각형 방 격자로 탈출 게임을 만든다. 각 방에는 북쪽, 남쪽, 동쪽, 서쪽으로 문이 하나씩 있다. 격자 경계에 있는 문은 밖으로 통하고, 나머지 문은 이웃한 방으로 통한다.

참가자는 정확히 $R \times C$명이고 방마다 한 명씩 들어간다. 게임이 시작되면 모든 문이 잠기고, 방마다 네 문 중 하나만 안쪽에서 열리도록 장치가 고정된다. 한 방에서 열리는 문은 게임이 끝날 때까지 그대로다. 두 방을 잇는 문이 한쪽에서는 열리고 반대쪽에서는 잠겨 있을 수도 있다.

참가자는 각자 따로 움직인다. 자기가 연 문으로만 지나갈 수 있고, 지나간 문은 뒤에서 닫힌다. 밖으로 통하는 문을 지나가면 탈출에 성공하고, $R \times C$번 움직여도 격자를 벗어나지 못하면 실패한다.

정확히 $K$명이 탈출하도록 방마다 열리는 문을 정하거나, 그렇게 정하는 방법이 없음을 판정한다.

첫 줄에 테스트 케이스 수 $T$가 주어진다. 이어지는 $T$개의 줄에 각각 세 정수 $R$, $C$, $K$가 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 정확히 $K$명이 탈출하는 배치가 없으면 IMPOSSIBLE, 있으면 POSSIBLE이다. POSSIBLE을 출력한 경우 이어서 $C$글자로 이루어진 줄을 $R$개 출력한다. 그중 $i$번째 줄의 $j$번째 글자는 $i$행 $j$열 방에서 열리는 문이 북쪽이면 N, 남쪽이면 S, 동쪽이면 E, 서쪽이면 W이다.

정확히 $K$명이 탈출하는 배치는 여러 개일 수 있으므로, 다음 규칙으로 만든 배치를 출력한다. $M = R \times C - K$로 둔다.

1. 방에 지그재그 순서로 번호를 붙인다. 1행은 왼쪽에서 오른쪽으로, 2행은 오른쪽에서 왼쪽으로, 3행은 다시 왼쪽에서 오른쪽으로 훑어 $p_1$부터 $p_{R \times C}$까지 정한다. 이 순서에서 이웃한 두 방은 항상 문 하나로 붙어 있다.
2. $i$가 1부터 $M - 1$까지일 때, 방 $p_i$에서는 $p_{i+1}$로 통하는 문이 열린다. 방 $p_M$에서는 $p_{M-1}$로 통하는 문이 열린다. $M = 0$이면 이 단계에서 정하는 방이 없다.
3. 남은 방에서는 모두 남쪽 문이 열린다.

• $1 \le T \le 100$
• $1 \le R \le 100$
• $1 \le C \le 100$
• $0 \le K \le R \times C$

탈출하지 못하는 참가자는 순환에 갇힌 것이다. 어느 방에서 출발하든 열리는 문을 따라가는 경로는 하나뿐이므로, 참가자는 밖으로 나가거나 같은 방들을 영원히 돈다. 그래서 $R \times C$번만 움직여 보면 모든 참가자의 결과가 정해진다.

방이 하나뿐인 격자에서는 어느 문이 열리든 밖으로 통하므로 그 참가자는 반드시 탈출한다.