Бесконечный лабиринт
Dr. Fukuoka разместил простого робота в двумерном лабиринте. Робот перемещается внутри лабиринта и никогда не выходит за его пределы, так как выхода нет.
Лабиринт представляет собой сетку размером H×W, как показано ниже. Верхняя сторона лабиринта обращена на север. Соответственно, правая, нижняя и левая стороны обращены на восток, юг и запад. Каждая ячейка либо пустая, либо стена и имеет координаты (i, j), где северо-западный угол имеет координаты (1, 1). Рядок i идет вниз к югу, а столбец j — к востоку.
Робот перемещается по пустым ячейкам и смотрит на север, восток, юг или запад. Он идет вперед, если перед ним пустая ячейка, и поворачивается на 90 градусов вправо, когда перед ним стена или край лабиринта. Он не может войти в ячейки со стенами. Он останавливается сразу после перемещения вперед на L ячеек.
Ваша задача — написать программу, которая, зная начальную позицию и направление робота, а также количество шагов, вычислит конечное положение и направление робота.
Входные данные
Входные данные состоят из последовательности наборов данных. Каждый набор данных имеет следующий формат.
H W L c_{1,1} c_{1,2} ... c_{1,W} ... c_{H,1} c_{H,2} ... c_{H,W}
Первая строка набора данных содержит три целых числа H, W и L (1 ≤ H, W ≤ 100, 1 ≤ L ≤ 10^18). Каждая из следующих H строк содержит ровно W символов. В i-й строке j-й символ c_{i,j} представляет ячейку в (i, j) лабиринта. "." обозначает пустую ячейку. "#" обозначает ячейку со стеной. "N", "E", "S", "W" обозначают робота на пустой ячейке, смотрящего на север, восток, юг и запад соответственно; это указывает на начальное положение и направление робота.
Можно предположить, что рядом с начальной позицией робота есть хотя бы одна пустая ячейка.
Конец ввода обозначается строкой с тремя нулями. Эта строка не является частью какого-либо набора данных.
Выходные данные
Для каждого набора данных выведите в строке конечный рядок, столбец и направление робота, разделенные одним пробелом. Направление должно быть одним из следующих: "N" (север), "E" (восток), "S" (юг) и "W" (запад).
Дополнительные пробелы или символы не допускаются.