Grid Escape

You are building an escape adventure inside a rectangular grid of rooms with $R$ rows and $C$ columns. Every room has four doors, one on each side: north, south, east, and west. A door on the border of the grid leads outside. Every other door connects two neighboring rooms.

Exactly $R \times C$ players play, one in each room. When the game starts, all doors lock and a mechanism fixes which door each room can open: in every room exactly one of the four doors opens from the inside, and that door stays the same for the whole adventure. A door between two rooms may open from one side and stay locked from the other side.

Each player moves on their own. A player may walk only through a door they opened themselves, and the door closes behind them. A player keeps walking through doors until they walk through a door that leads outside, which means they escaped, or until they have made $R \times C$ moves without leaving the grid, which means they failed.

Choose the door that opens in each room so that exactly $K$ players escape, or report that no choice does that.

The first line has the number of test cases, $T$. Each of the next $T$ lines has three integers $R$, $C$, and $K$.

For each test case, print one line in the form Case #x: y. Here x is the test case number starting from 1, and y is IMPOSSIBLE when no arrangement lets exactly $K$ players escape, or POSSIBLE when one does. After a POSSIBLE line, print $R$ more lines of $C$ characters each. The $j$-th character of the $i$-th of those lines is N, S, E, or W, telling which door opens in the room in row $i$, column $j$.

Several arrangements can let exactly $K$ players escape, so print the one built by the following rule. Let $M = R \times C - K$.

1. Number the rooms in zigzag order: row 1 from left to right, row 2 from right to left, row 3 from left to right again, and so on, giving $p_1$ through $p_{R \times C}$. Two rooms next to each other in this order always share a door.
2. For $i$ from 1 to $M - 1$, the room $p_i$ opens the door leading to $p_{i+1}$. The room $p_M$ opens the door leading to $p_{M-1}$. When $M = 0$, this step fixes no room.
3. Every remaining room opens its south door.

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

A player who does not escape is stuck in a loop. From any room the open doors give one path forward, so a player either reaches the outside or walks the same set of rooms forever. That is why $R \times C$ moves are enough to settle every player.

In a grid with a single room, the one door that opens leads outside, so that player always escapes.