Cədvəlin çevrilməsi

Vanya böyük məlumatlarla işləyir və onun layihəsi nəhəng statistik məlumat cədvəllərinin emalı ilə bağlıdır. O, cədvəllərin sətir, sütun və hüceyrələrinin yerini dəyişdirən çevirmə modulunun hazırlanmasına cavabdehdir.

Modul h sətir və w sütundan ibarət cədvəli emal edir. Sətirlər yuxarıdan aşağıya doğru 0-dan h - 1-ə qədər, sütunlar isə soldan sağa doğru 0-dan w - 1-ə qədər nömrələnir. Cədvəlin i-ci sətrində, j-ci sütunundakı hüceyrə [i, j] kimi göstərilir. Başlanğıcda [i, j] hüceyrəsi i * w + j ədədini ehtiva edir.

Şəkil 1-də h = 3, w = 5 üçün cədvəlin başlanğıc doldurulmasının nümunəsi göstərilmişdir.

Cədvəl çevirmə modulu aşağıdakı üç növ əməliyyatı yerinə yetirə bilər.

Şəkil 2-də yuxarıda göstərilən cədvəlin «c 0 1», «r 0 1», «f 0 0 1 2» əməliyyatları ardıcıllığı yerinə yetirildikdən sonra necə göründüyü göstərilmişdir.

Bütün əməliyyatlar yerinə yetirildikdən sonra Vanya cədvəl üçün nəzarət cəmini hesablayır: bütün hüceyrələr [i, j] üzrə (v[ij] * 17^i * 19^j) mod (10^9 + 7) dəyərlərinin cəmi. Burada v[ij] [i, j] hüceyrəsindəki dəyəri ifadə edir və «mod» əməliyyatı qalıq alma əməliyyatını göstərir. Məsələn, nümunədəki cədvəl üçün nəzarət cəmi belə hesablanır: (6 * 17^0 * 19^0 + 2 * 17^0 * 19^1 + ... + 14 * 17^2 * 19^4) mod (10^9 + 7) = 564 830 737.

Vanyaya bütün əməliyyatları yerinə yetirməkdə və nəticədə alınan cədvəlin nəzarət cəmini hesablamaqda kömək edin.

Bu məsələnin giriş məlumatları birbaşa verilə bilməyəcək qədər böyük olduğundan, giriş üçün massiv genişləndirmə proseduruna ehtiyacınız olacaq. Bu prosedur məsələnin həllində istifadə olunmalı xüsusi xüsusiyyətlərə malik deyil, nəzərdə tutulan münsiflər heyətinin həlli bu məsələdə bütün massivləri açıq şəkildə yaradır və sonra onlarla elə işləyir ki, sanki onları giriş məlumatlarından oxuyur.

Uzunluğu n olan massiv 2 ≤ k ≤ n uzunluğunda massiv əsasında necə yaradılır, təsvir edək. Tutaq ki, A = (a[1], a[2], ..., a[k]) tam müsbət olmayan ədədlər massividir. Ax = (ax[1], ax[2], ..., ax[n]) tam ədədlər massivini A massivinin r moduluna qədər n ölçüsünə genişlənməsi adlandıracağıq, əgər onun elementləri aşağıdakı düsturlarla hesablanırsa.

• Əgər 1 ≤ i ≤ k, onda ax[i] = a[i].

• Əgər k + 1 ≤ i ≤ n, onda ax[i] = (10007 * ax[i-2] + 10009 * ax[i-1] + 87277) mod r.

Burada «mod» da r moduluna qalıq alma əməliyyatını göstərir. Məsələn, A = (1, 4, 3) massivini 13 moduluna qədər 5 elementə genişləndirək.

ax[1] = a[1] = 1.

ax[2] = a[2] = 4.

ax[3] = a[3] = 3.

ax[4] = (10007 * ax[2] + 10009 * ax[3] + 87277) mod 13 = 157332 mod 13 = 6.

ax[5] = (10007 * ax[3] + 10009 * ax[4] + 87277) mod 13 = 177352 mod 13 = 6.

Beləliklə, Ax = (1, 4, 3, 6, 6).

Giriş məlumatları

Girişin ilk sətiri cədvəlin ölçülərini və yerinə yetirilməli olan çevirmə sayını göstərən h, w, n ədədlərini ehtiva edir (1 ≤ h, w ≤ 5 000, 2 ≤ n ≤ 10^6).

İkinci sətir n uzunluğunda s sətrini ehtiva edir - çevirmə növlərinin ardıcıllığı, s[i] = «c» sütunların dəyişdirilməsi əməliyyatını, s[i] = «r» sətirlərin dəyişdirilməsi əməliyyatını, s[i] = «f» hüceyrələrin dəyişdirilməsi əməliyyatını göstərir.

Növbəti dörd sətir müvafiq olaraq A, B, C, D massivlərini müəyyən edir. Hər bir massiv k ədədini ehtiva edir, 2 ≤ k ≤ n, k ≤ 1000, sonra isə massiv elementləri gəlir. A və C massivlərinin elementləri 0 ≤ a[i], c[i] ≤ h - 1, B və D massivlərinin elementləri 0 ≤ b[i], d[i] ≤ w - 1 məhdudiyyətinə cavab verir.

Tutaq ki, Ax A massivinin h moduluna qədər n ölçüsünə genişlənməsidir, Bx B massivinin w moduluna qədər n ölçüsünə genişlənməsidir, Cx C massivinin h moduluna qədər n ölçüsünə genişlənməsidir və Dx D massivinin w moduluna qədər n ölçüsünə genişlənməsidir.

Cədvəl üzərində yerinə yetirilməli olan əməliyyatlar aşağıdakı kimi müəyyən edilir: i-ci əməliyyatın növü s[i] simvolu ilə müəyyən edilir və parametrlər Ax, Bx, Cx, Dx massivlərindən alınır.

• Əgər s[i] = «c», onda i-ci əməliyyat «c Bx[i] Dx[i]»;

• Əgər s[i] = «r», onda i-ci əməliyyat «r Ax[i] Cx[i]»;

• Əgər s[i] = «f», onda i-ci əməliyyat «f Ax[i] Bx[i] Cx[i] Dx[i]»;

Çıxış məlumatları

Bütün çevirmələr yerinə yetirildikdən sonra cədvəlin nəzarət cəmini göstərən bir ədəd çıxarın.

Nümunələr