Hiyləgər ninja#3120
Böyük bir sarayda bir zal var, burada döşəmə (2n-1) \times (2n-1) ölçülü kvadratlar şəbəkəsindən ibarətdir; kvadratlar (2n-1) sətrə (1-dən 2n-1-ə qədər nömrələnmiş) və (2n-1) sütuna (1-dən 2n-1-ə qədər nömrələnmiş) bölünmüşdür — aşağıdakı şəkildə n = 4 üçün göstərilmişdir. Hər bir kvadrat, əgər həm sətri, həm də sütunu cütdürsə, taxta dayaqlı böyük kvadrat sütunla örtülüdür. Qalan kvadratlar boşdır. Beləliklə, divarlarla və taxta dayaqlarla birlikdə, zal boyunca soldan sağa və öndən arxaya olmaqla hər istiqamətdə dəhliz əmələ gəlir. Arxa divarın sonundakı öndən-arxaya dəhlizlərin çıxışında pərdəli qapılar var. Digər yerlərdə divarlar tam bağlıdır.
Zal mühafizəçi tərəfindən qorunur. Hər mühafizəçi bir öndən-arxaya və bir soldan-sağa dəhlizin kəsişməsində dayanır. Hər bir mühafizəçi saniyə sola, saniyə arxaya, saniyə sağa, saniyə önə baxır və bu dövrü sonsuza qədər təkrarlayır. Mühafizəçilərin baxış istiqamətləri bir-biri ilə sinxron olmaya bilər: bəziləri sola baxanda, digərləri qabağa baxa bilər.
Bir ninja mühafizəçilər tərəfindən görünmədən zaldan ön tərəfdən arxa tərəfə keçməlidir. Ninja zalın içinə girmədən əvvəl 0-cı sətrdə, yəni ön divardakı pərdələrdən birinin arxasında gözləyir. Ninja hansı pərdənin arxasında gözləyəcəyinə və zalın içərisinə daxil olmadan öncə nə qədər gözləyəcəyinə özü qərar verir. Ninja çıxış üçün istənilən arxa divar qapısını da seçə bilər. İki qonşu kvadrat arasında hərəkət etmək üçün ninjaya dəqiq saniyə lazımdır — bu zaman hərəkət edən ninja, həmin istiqamətə baxan istənilən mühafizəçi tərəfindən görünə bilər. Ninja zalın içərisindən keçə bilərmi? Mühafizəçilər bir-birlərindən aralı olsa da, qarşısı açıqdır və bir-birinin ardınca baxa bilirlər, amma pərdədən baxa bilmirlər.
Şəkil 1-də göstərilib ki, ninja çıxışa necə yol tapır. Əvvəlcə ninja gözləyir. 8-ci saniyədə 5-ci sətr, 1-ci sütundakı mühafizəçi sola baxır və ninja pərdənin arxasından çıxır. 10-cu saniyədə ninja 1-ci sətr, 1-ci sütuna çatır. 12-ci saniyədə ninja 2-ci sətr, 1-ci sütuna çatır. Ninja 3-cü sətr, 5-ci sütundakı mühafizəçi arxaya baxana qədər gözləyir; sonra hərəkətə başlayır və 1-ci sətrdəki mühafizəçi o istiqamətə baxmazdan əvvəl 3-cü sütundakı pərdənin arxasında yox olur.
Birinci sətirdə testlərin sayı verilir. Hər test üçün aşağıdakı formatda məlumat verilir:
Birinci sətirdə iki ədəd var: (hər istiqamətdə dəhlizlərin sayı, 1 \leq n \leq 250) və (mühafizəçilərin sayı, 0 \leq k \leq 500).
Növbəti sətirdə — hər mühafizəçi üçün bir sətir: hər birində bir tək (1 \leq r \leq 2n-1), bir tək (1 \leq c \leq 2n-1) və bir , , və ya hərfi verilir. Birinci ədəd mühafizəçinin yerləşdiyi sətr, ikinci ədəd yerləşdiyi sütundur, hərf isə başlanğıcda baxdığı istiqaməti göstərir (sol, arxa, sağ, ön).
Zalın heç bir mövqeyində birdən artıq mühafizəçi olmur.
Hər test üçün ayrıca bir sətirdə **succeeds** və ya **fails** sözünü çap edin.
Nümunə 1