Нескінченний Лабіринт#3593
Др. Фукуока розмістив простого робота в двовимірному лабіринті. Робот пересувається всередині лабіринту і ніколи не виходить за його межі, оскільки виходу немає.
Лабіринт складається з H \times W клітинок, як показано нижче. Верхня сторона лабіринту орієнтована на північ. Відповідно, права, нижня та ліва сторони орієнтовані на схід, південь і захід. Кожна клітинка або порожня, або стіна, і має координати , де північно-західний кут має координати . Рядок йде вниз на південь, а стовпець — на схід.
Робот рухається по порожніх клітинках і може бути орієнтований на північ, схід, південь або захід. Він рухається вперед, якщо перед ним є порожня клітинка, і повертає на градусів вправо, якщо перед ним стіна або край лабіринту. Він не може увійти в клітинки-стіни. Робот зупиняється відразу після того, як пройде вперед на клітинок.
Ваше завдання — маючи початкову позицію та напрямок робота, а також кількість кроків, написати програму, яка обчислить кінцеву позицію та напрямок робота.
Вхідні дані складаються з кількох наборів. Кожен набір даних має такий формат:
H W L c_{1,1} c_{1,2} ... c_{1,W} ... c_{H,1} c_{H,2} ... c_{H,W}
Перший рядок набору даних містить три цілі числа , і (1 \leq H, W \leq 100, 1 \leq L \leq 10^{18}). Кожен з наступних рядків містить рівно символів. У -му рядку -й символ c_{i,j} представляє клітинку в лабіринту. "." позначає порожню клітинку. "#" позначає клітинку-стіну. "N", "E", "S", "W" позначають робота на порожній клітинці, орієнтованого на північ, схід, південь і захід відповідно; це вказує на початкову позицію та напрямок робота.
Ви можете припустити, що є принаймні одна порожня клітинка, суміжна з початковою позицією робота.
Кінець вводу позначається рядком з трьома нулями. Цей рядок не є частиною жодного набору даних.
Для кожного набору даних виведіть у рядок кінцевий рядок, стовпець і напрямок робота, розділені одним пробілом. Напрямок має бути одним з наступних: "N" (північ), "E" (схід), "S" (південь) і "W" (захід).
Додаткові пробіли або символи не допускаються.
Приклад 1