Robot Naviqasiyası
Bir robot uzaq bir planeti araşdırmaq üçün göndərilib. Robotun hansı yolu izləməli olduğunu müəyyən etmək üçün hər gün bir proqram göndərilir. Proqram aşağıdakı əmrlər ardıcıllığından ibarətdir:
İRƏLİ: bir vahid irəli hərəkət et.
SOL DÖN: 90 dərəcə sola dön. Robot eyni yerdə qalır.
SAĞ DÖN: 90 dərəcə sağa dön. Robot eyni yerdə qalır.
Robot həmçinin ətraf mühitin xəritəsini əldə etməyə imkan verən sensor vahidlərinə malikdir. Xəritə M sətir və N sütundan ibarət bir şəbəkə kimi təmsil olunur. Hər bir şəbəkə nöqtəsi (r, c) koordinatı ilə təmsil olunur, burada r = 0 xəritənin şimal kənarı, r = M - 1 cənub kənarı, c = 0 qərb kənarı və c = N - 1 şərq kənarıdır. Bəzi şəbəkə nöqtələri təhlükələr (məsələn, kraterlər) ehtiva edir və proqram bu nöqtələrdən qaçmalı və ya robotu itirmək riskini daşımalıdır.
Əgər robotun ilkin yeri və istiqaməti, həmçinin təyinat mövqeyi məlumdursa, biz robotu təyinat yerinə aparmaq üçün ən qısa proqramı (ən az əmr olan) göndərmək istəyirik (təyinat yerində hansı istiqamətə baxdığı bizi maraqlandırmır). Siz robotu təyinat yerinə aparacaq müxtəlif ən qısa proqramların sayını bilməkdə daha çox maraqlısınız, çünki planetlərarası rabitə mütləq etibarlı deyil və fərqli ardıcıllıqlar göndərməli ola bilərik. Lakin, ən qısa proqramların sayı çox böyük ola bilər, buna görə də siz qalıq kimi bir modula görə sayını hesablamaqla kifayətlənirsiniz, dərslərdə öyrəndiyiniz Çin qalıq teoremi adlı bir şeyin son cavabı hesablamaq üçün istifadə edilə biləcəyini bilirsiniz.
Giriş verilənləri
Giriş bir neçə haldan ibarətdir. Hər bir halın ilk sətri üç tam ədəd M, N və modul m (0< M, N ≤ 1000, 0 < m ≤ 1000000000) verir. Növbəti M sətir hər biri N simvolu ehtiva edir və xəritəni müəyyən edir. '.' robotun həmin şəbəkə nöqtəsinə hərəkət edə biləcəyini göstərir və '*' təhlükəni göstərir. Sonuncu sətir dörd tam ədəd r_1, c_1, r_2, c_2 və bir simvol d verir. Koordinatlar (r_1, c_1) robotun ilkin mövqeyini, (r_2, c_2) isə təyinatı göstərir. Simvol d robotun ilkin istiqamətini göstərən 'N', 'S', 'W', 'E' simvollarından biridir. İlkin mövqe və təyinatın təhlükə olmadığı qəbul edilir.
Giriş m = 0 olduqda bitir.
Çıxış verilənləri
Hər bir hal üçün, halın nömrəsini, modulu və modula m bölündükdə fərqli proqramların sayının qalığını çap edin. Hər bir halın çıxışı aşağıda göstərilən formatda bir sətirdə olmalıdır. Əgər robotu təyinat yerinə aparacaq heç bir proqram yoxdursa, fərqli proqramların sayı üçün -1 çıxış edin.