Infinity Maze

A simple robot sits inside a two-dimensional maze. The maze has no exit, so the robot never leaves it.

The maze is made of H × W grid cells. The upper side of the maze faces north, so the right, lower and left sides face east, south and west. Each cell is either empty or a wall, and it has coordinates $(i, j)$ where the north-west corner is $(1, 1)$. The row index $i$ grows toward the south and the column index $j$ grows toward the east.

The robot stands on an empty cell and faces north, east, south or west. When the cell directly in front of it is empty, it moves one cell forward. When a wall cell is in front of it, or the front is outside the maze, it turns 90 degrees to the right in place. It cannot enter a wall cell. It stops right after it has moved forward $L$ times. A turn does not count as a forward move.

Given the initial position and direction of the robot and the number of forward moves $L$, compute the position where the robot stops and the direction it faces there.

The input is a sequence of datasets. Each dataset has the following form.

H W L
c(1,1)c(1,2) ... c(1,W)
...
c(H,1)c(H,2) ... c(H,W)

The first line of a dataset contains three integers H, W and L ($1 \le H, W \le 100$, $1 \le L \le 10^{18}$).

Each of the following H lines contains exactly W characters. In line $i$, the $j$-th character $c_{i,j}$ describes the cell at $(i, j)$. "." is an empty cell and "#" is a wall cell. "N", "E", "S" and "W" mark a robot standing on an empty cell and facing north, east, south and west respectively, and they give the initial position and direction of the robot.

You may assume that at least one empty cell is adjacent to the initial position of the robot.

A line with three zeros ends the input. That line is not part of any dataset.

For each dataset, print the final row index, column index and direction of the robot on one line, separated by single spaces. The direction is one of "N" (north), "E" (east), "S" (south) and "W" (west).

Print no extra spaces or characters.