Robot Naviqasiyası
Aparat uzaq bir planetə kəşfiyyat məqsədilə göndərilib. Hər gün aparata hansı yolu izləməli olduğunu bildirmək üçün bir proqram göndərilir. Bu proqram aşağıdakı əmrlərdən ibarətdir:
İRƏLİ: bir vahid irəli hərəkət et.
SOL DÖN: 90 dərəcə sola dön. Aparat eyni yerdə qalır.
SAĞ DÖN: 90 dərəcə sağa dön. Aparat eyni yerdə qalır.
Aparat, ətraf mühitin xəritəsini əldə etməyə imkan verən sensorlarla təchiz olunub. Xəritə M sətir və N sütundan ibarət bir şəbəkə kimi təsvir edilir. Hər bir şəbəkə nöqtəsi (r, c) koordinatları ilə göstərilir, 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 aparatı itirmək riski ilə üzləşməlidir.
Əgər aparatın başlanğıc yeri və istiqaməti, həmçinin təyinat yeri məlumdursa, biz aparatı təyinat yerinə çatdırmaq üçü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). Lakin, siz aparatı təyinat yerinə çatdırmaq üçün neçə fərqli ən qısa proqramın olduğunu bilməkdə daha çox maraqlısınız, çünki planetlərarası rabitə mütləq etibarlı deyil. Ən qısa proqramların sayı çox böyük ola bilər, buna görə də siz qalıq olaraq bir modula görə sayını hesablamaqla kifayətlənirsiniz. Dərslərdə öyrəndiyiniz Çin qalıq teoremi adlanan 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. '.' simvolu aparatin həmin şəbəkə nöqtəsinə hərəkət edə biləcəyini göstərir və '*' simvolu təhlükəni göstərir. Sonuncu sətir dörd tam ədəd r1, c1, r2, c2 və bir simvol d verir. Koordinatlar (r1, c1) aparatın ilkin mövqeyini, (r2, c2) isə təyinat yerini göstərir. Simvol d aparatın ilkin istiqamətini göstərən 'N', 'S', 'W', 'E' simvollarından biridir. İlkin mövqe və təyinat yerinin təhlükə olmadığı qəbul edilir. Giriş m = 0 olduqda sona çatır.
Çıxış verilənləri
Hər bir hal üçün, halın nömrəsini, modulu və modula 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 aparatı təyinat yerinə apara biləcək heç bir proqram yoxdursa, fərqli proqramların sayı üçün -1 çıxış edin.