0398 - だんじょん

問題

縦 H × 横 W の二次元の格子状のだんじょんがある. だんじょんの上側は北を向いている.
わたしは, だんじょんで遊ぶ.
この遊びの 1 ステップは以下の行動からなる.

• 自分が向いている方向に1マス進む.
• ただし進む先がダンジョンの外や障害物であれば, その場にとどまり右に90度回転する. ステップ数にはカウントしない.

L ステップ後, わたしがどこにいてどこを向いているか知りたい.

入力

入力は複数のデータセットからなる. それぞれのデータセットは以下の形式で与えられる.

H W L
C1,1C1,2...C1,W
:
CH,1CH,2...CH,W

• 1 行目にダンジョンの縦幅 H, 横幅 W, ステップ数 L が与えられる.
• 2 行目から H 行にかけて, ダンジョンの各マスの情報が与えられる. 各マス C_i,j は以下のいずれかで与えられる.
• '.': 何もない.
• '#': 障害物.
• 'N', 'E', 'S', 'W': わたしの初期位置と向いている方向. 方向は 'N'(North:北), 'E'(East:東), 'S'(South:南), 'W'(West:西) を向いていることを表す.

入力の終わりは 3 つの 0 で表される.

制約

• 1 ≤ H, W ≤ 100
• 1 ≤ L ≤ 10¹⁸ (オーバーフローに注意すること.)
• わたしの初期位置に隣接した少なくとも 1 つのマスは, 何もないセルである.

出力

L ステップ後のわたしの位置と向きの情報を, 何行目, 何列目, 向き の順で半角空白区切りで出力せよ.

位置は, 左上のマスが 1 行目 1 列目で, 右下のマスが H 行目 W 列目である.

向きは, 'N'(North:北), 'E'(East:東), 'S'(South:南), 'W'(West:西) のうちのいずれか 1 文字である.

入出力例

入力例

3 3 10
E..
.#.
...
5 5 19
####.
.....
.#S#.
...#.
#.##.
5 5 6
#.#..
#....
##.#.
#..S.
#....
5 4 35
..##
....
.##.
.#S.
...#
0 0 0

出力例

1 3 E
4 5 S
4 4 E
1 1 N