问题
당신은 R행 C열의 직사각 격자 방(단위 칸)으로 이루어진 새로운 "탈출" 어드벤처를 설계하고 있다. 각 방에는 격자의 네 직교 방향(북, 남, 동, 서)에 대응하는 네 개의 문이 있다. 격자 경계에 있는 문은 바깥으로 이어지고, 그 외의 문은 다른 방으로 이어진다.
이 어드벤처는 정확히 R × C명의 플레이어가 플레이하며, 각 플레이어는 서로 다른 R × C개의 방 중 하나에서 시작한다. 모두 자리에 들어가 게임이 시작되면, 모든 문이 닫히고 기계적인 장치가 작동한다: 각 방에서 네 개의 문 중 하나는 그 방 안쪽에서 열 수 있고, 나머지 세 개의 문은 열 수 없다. 이는 어드벤처 내내 일관되며, 어떤 방에서든 열 수 있는 문은 항상 같은 문이다. 두 방을 연결하는 문이 한쪽에서는 열리지만 다른 쪽에서는 열리지 않을 수도 있다는 점에 유의하라.
각 플레이어는 다른 모든 플레이어와 독립적으로 움직인다. 플레이어는 자신이 직접 연 문으로만 통과할 수 있으며, 문을 통과한 뒤에는 문을 닫아야 한다. 각 플레이어는 바깥으로 이어지는 문을 통과해 탈출하거나, 탈출하지 못한 채로 R × C번 이동할 때까지 계속 문을 통과한다. (후자의 경우 그 플레이어는 실패한 것으로 간주되며 탈출하지 못한다.)
당신은 각 방에서 어떤 문이 열리도록 할지 정해서,
정확히 K명의 플레이어만 탈출할 수 있게 하고 싶다.
그렇게 하는 방법을 찾거나,
불가능하다면 IMPOSSIBLE을 출력하라.
输入
입력의 첫 줄에는 테스트 케이스 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 위에서 설명한 정수 R, C, K가 주어진 한 줄로 이루어진다.
输出
각 테스트 케이스마다 먼저 Case #x: y 형식의 한 줄을 출력하라.
여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고,
해가 없다면 y는 IMPOSSIBLE,
해가 있다면 y는 POSSIBLE이다.
해가 있다면, 추가로 R줄을 출력하라.
각 줄은 길이 C의 문자열이며 방 격자를 나타낸다.
i번째 줄의 j번째 문자는 i번째 행 j번째 열의 방을 나타내고,
각 문자는 그 방에서 열리는 문이 북/남/동/서 중 어디로 이어지는지에 따라
영문 대문자 N, S, E, W 중 하나여야 한다.
가능한 답이 여러 개라면 그중 아무 것이나 출력해도 된다.
示例
2
2 3 2
1 1 0
Case #1: POSSIBLE
SES
SNW
Case #2: IMPOSSIBLE
需要登录才能编写代码。