Garbling Oyunu
Pavel tam ədədlərdən ibarət matrislə yeni bir oyun icad edib. O, r x c ölçülü, r sıra və c sütundan ibarət matris götürür və 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). Daha sonra, o, aşağıda izah olunan qaydalara uyğun olaraq matrisdəki ədədləri yenidən düzəldir və ayrı bir kağız parçasına ədədlərin ardıcıllığını yazır. O, bu prosesi matrisin qarışdırılması adlandırır.
Yenidən düzəltmə qaydaları qarışdırma xəritəsi ilə müəyyən edilir ki, bu da r - 1 x (c - 1) ölçülü L, R və N hərflərindən ibarət matrisdir. Aşağıda başlanğıc 4 x 5 ölçülü matris və onun üçün nümunə 3 x 4 ölçülü qarışdırma xəritəsi göstərilmişdir.
Pavel matrisin qarışdırılmasını bir sıra gedişlərdə həyata keçirir. İlk gedişində Pavel birinci sıranın və birinci sütunun ədədini götürür (aydınlıq üçün yuxarıdakı şəkildə mötərizəyə alınmışdır) və onu yazır.
Ədədi yazdıqdan sonra o, bir qarışdırma gedişi həyata keçirir:
Pavel, yazdığı ədədin mövqeyinə uyğun gələn qarışdırma xəritəsindəki hərfə baxır (ilk gedişdə bu, yuxarı-sol küncdəki hərfdir). Qarışdırma xəritəsindəki hərfə görə, matrisin yuxarı-sol küncü yazdığı ədədi ehtiva edən 2x2 blok aşağıdakı şəkildə yenidən düzəldilir:
- R – blok sağa doğru fırladılır.
- L – blok sola doğru fırladılır.
- N – Pavel bu gedişdə matrisi dəyişmir.
İkinci gedişdə Pavel birinci sıranın ikinci sütunundakı ədədi götürür, onu yazır və qarışdırma gedişini həyata keçirir və s. c - 1 gedişdə o, birinci sıranı bitirir və ikinci sıraya keçir və s. soldan sağa və yuxarıdan aşağıya doğru davam edir. (r - 1)(c - 1) gedişdə o, (r - 1)(c - 1) ədədi yazır və bütün matrisi qarışdırır, beləliklə, o, yenidən yuxarı-sol küncdən başlayır və matrisi soldan sağa və yuxarıdan aşağıya doğru qarışdırmağa davam edir.
Aşağıdakı matrislər nümunə qarışdırma xəritəsi ilə ilk dörd gedişin təsirini göstərir.
İlk 4 gedişdə aşağıdakı ədədlər ardıcıllığı yazılır: 1 7 7 9. 5-ci gedişdə ikinci sıranın və birinci sütunun ədədi yazılır, lakin matris dəyişməz qalır, çünki qarışdırma xəritəsinin ikinci sıranın və birinci sütunununda N var. Altı gedişdə Pavel 1 7 7 9 1 8 alır.
Qarışdırma xəritəsi və Pavelin bu oyunda etdiyi gedişlərin sayı verildikdə, Pavelin hər bir ədədi neçə dəfə yazdığını tapın. Cavabı 10^5 modulunda verməlisiniz.
Giriş verilənləri
Giriş faylının birinci sətri üç tam ədəd ehtiva edir – r, c, və n, burada r, c (2 ≤ r, c ≤ 300) başlanğıc matrisin ölçüləridir, n (0 ≤ n < 10^100) Pavelin etdiyi gedişlərin sayıdır.
Sonrakı r - 1 sətir qarışdırma xəritəsini c - 1 hərfləri R, L, və ya N ilə ehtiva edir.
Çıxış verilənləri
Çıxış faylına rc sətir yazın, hər sətirdə bir tam ədəd. i-ci sətirdə Pavelin n gedişi zamanı i ədədinin neçə dəfə yazıldığını 10^5 modulunda yazın.