Sonsuzluq Labirinti
Dr. Fukuoka ikiölçülü labirintə sadə bir robot yerləşdirib. Robot labirintdə hərəkət edir və çıxış olmadığı üçün heç vaxt labirintdən çıxmır.
Labirint H×W ölçülü şəbəkə hüceyrələrindən ibarətdir, yuxarı tərəfi şimala baxır. Beləliklə, sağ, aşağı və sol tərəflər müvafiq olaraq şərq, cənub və qərbə baxır. Hər bir hüceyrə ya boşdur, ya da divardır və (i, j) koordinatlarına malikdir, burada şimal-qərb küncü (1, 1) nöqtəsindədir. i sətiri cənuba doğru, j sütunu isə şərqə doğru gedir.
Robot boş hüceyrələrdə hərəkət edir və şimala, şərqə, cənuba və ya qərbə baxır. Qarşısında boş hüceyrə olduqda irəliləyir, divar hüceyrəsinə və ya labirintin kənarına gəldikdə isə sağa 90 dərəcə dönür. Divar hüceyrələrinə daxil ola bilmir. L hüceyrə irəlilədikdən dərhal sonra dayanır.
Sizin vəzifəniz, robotun başlanğıc mövqeyi və istiqaməti, həmçinin addımların sayı verildikdə, robotun son mövqeyini və istiqamətini hesablamaq üçün bir proqram yazmaqdır.
Giriş verilənləri
Giriş məlumat dəstlərinin ardıcıllığıdır. Hər bir məlumat dəsti aşağıdakı kimi formatlanır:
H W L c_{1,1} c_{1,2} ... c_{1,W} ... c_{H,1} c_{H,2} ... c_{H,W}
Bir məlumat dəstinin ilk sətri üç tam ədəd H, W və L (1 ≤ H, W ≤ 100, 1 ≤ L ≤ 10^18) ehtiva edir. Növbəti H sətirdən hər biri dəqiq W simvol ehtiva edir. i-ci sətirdə, j-ci simvol c_{i,j} labirintin (i, j) nöqtəsindəki hüceyrəni təmsil edir. "." boş hüceyrəni göstərir. "#" divar hüceyrəsini göstərir. "N", "E", "S", "W" isə müvafiq olaraq şimala, şərqə, cənuba və qərbə baxan robotu göstərir; bu, robotun başlanğıc mövqeyini və istiqamətini göstərir.
Robotun başlanğıc mövqeyinə bitişik ən azı bir boş hüceyrənin olduğunu qəbul edə bilərsiniz.
Girişin sonu üç sıfırdan ibarət bir sətrlə göstərilir. Bu sətr heç bir məlumat dəstinə daxil deyil.
Çıxış verilənləri
Hər bir məlumat dəsti üçün robotun sonuncu sətirini, sütununu və istiqamətini bir sətrdə, bir boşluqla ayrılmış şəkildə çıxarın. İstiqamət aşağıdakılardan biri olmalıdır: "N" (şimal), "E" (şərq), "S" (cənub) və "W" (qərb).
Əlavə boşluqlar və ya simvollar icazəli deyil.