Qarmaqarışdırma Oyunu

Pavel tam ədədli matris üzərində yeni bir oyun icad edib. O, $r$ sətr və $c$ sütundan ibarət bir r \times c matris götürür, onu soldan sağa və yuxarıdan aşağıya doğru $1$-dən $rc$-yə qədər olan ədədlərlə doldurur ($1$ yuxarı-sol küncdə, $rc$ isə aşağı-sağ küncdə yerləşir). Sonra isə, aşağıda təsvir edilən qaydalara əsasən, matrisi yenidən düzür və seçilmiş ədədləri ayrıca bir kağıza yazır. O, bu prosesi matrisin qarmaqarışdırılması adlandırır.

Yenidən düzülmə qaydaları isə qarmaqarışdırma xəritəsi adlı (r - 1) \times (c - 1) ölçülü, L, R və N hərflərindən ibarət bir matrisa ilə təyin olunur. Aşağıda ilkin 4 \times 5 matris nümunəsi və 3 \times 4 ölçülü bir qarmaqarışdırma xəritəsi göstərilib.

Pavel matrisi bir sıra addımlarla qarmaqarışdırır. İlk addımda Pavel birinci sətirin və birinci sütunun hüceyrəsindəki ədədi (yuxarıda mötərizədə göstərilib) götürüb yazır.

Ədədi yazdıqdan sonra belə bir qarmaqarışdırma addımı yerinə yetirir:

Pavel indicə yazılan ədədin mövqeyinə uyğun gələn qarmaqarışdırma xəritəsindəki hərfə baxır (birinci addımda bu, xəritənin yuxarı-sol küncündəki hərfdir). Qarmaqarışdırma xəritəsindəki hərfə əsasən, matricdə yuxarı-sol küncündə indicə yazılmış ədəd olan 2\times2-lik blok aşağıdakı kimi yenidən düzülür:

- R — blok saat əqrəbi istiqamətində fırlanır. - L — blok saat əqrəbi istiqamətinin əksinə fırlanır. - N — bu addımda Pavel matrisi dəyişmir.

İkinci addımda Pavel birinci sətirin ikinci sütunundakı ədədi yazır və qarmaqarışdırma addımını həyata keçirir və s. c-1 addımdan sonra, o, birinci sətri bitirir və ikinci sətrə keçir, yenə də soldan sağa və yuxarıdan aşağıya davam edir. (r - 1)(c - 1) addımdan sonra o, (r - 1)(c - 1) ədəd yazır və bütün matrisi qarmaqarışdırır, sonra isə yuxarı-sol küncdən başlayıb matrisi bir daha soldan sağa və yuxarıdan aşağıya qarmaqarışdırmağa davam edir.

Aşağıdakı matrislər nümunə qarmaqarışdırma xəritəsindən istifadə edilən ilk dörd addımın təsirini göstərir.

İlk 4 addımda aşağıdakı ədədlər yazılıb: $1779$. 5-ci addımda isə ikinci sətirin birinci sütunundakı ədəd yazılıb, lakin matris dəyişməz qalıb, çünki qarmaqarışdırma xəritəsində həmin mövqedə N var. 6 addımda Pavel 1~7~7~9~1~8 yazır.

Qarmaqarışdırma xəritəsi və oyunda Pavelin etdiyi addımların sayı verildikdə, hər bir ədədin Pavel tərəfindən neçə dəfə yazıldığını müəyyən edin. Cavabı 10^5-ə görə çıxışa verin.