wind

Gigel a intrat din nou în belele! El se află într-o matrice cu $N$ linii și $M$ coloane numerotate de la $1$ la $N$ și respectiv de la $1$ la $M$. Asupra fiecărei celule acționează un vânt foarte puternic care îl împinge către una dintre celulele vecine. Mai exact, dacă la un moment dat Gigel se află în celula $(i, j)$, vântul îl va "lua pe sus" și îl va purta astfel încât după o secundă să ajungă în celula vecină indicată de direcția vântului din celula curentă, după cum urmează:

• N (Nord) $\rightarrow$ ajunge în celula $(i - 1, j)$
• S (Sud) $\rightarrow$ ajunge în celula $(i + 1, j)$
• E (Est) $\rightarrow$ ajunge în celula $(i, j + 1)$
• V (Vest) $\rightarrow$ ajunge în celula $(i, j - 1)$

Fiecare celulă din matrice conține o livadă de meri ce produce $a[i][j]$ mere, inițial $a[i][j] = (i - 1) \cdot M + j$. Gigel va colecta aceste mere de fiecare dată când ajunge în celula $(i, j)$. De-a lungul timpului, direcția vântului se poate schimba în anumite celule, de asemenea cantitățile de mere din livezi se pot actualiza. Voi va trebui să răspundeți la o serie de interogări pentru a-l ajuta pe Gigel să afle câte mere ar colecta dacă s-ar lăsa pradă vântului pentru un număr dat de secunde. Avem astfel $Q$ evenimente de trei tipuri:

• 1 i j d → Actualizare vânt: Direcția vântului din celula $(i, j)$ devine $d \in \{$N, S, E, V$\}$.
• 2 l r val → Actualizare mere din livadă: Toate livezile $a[i][j]$ cu $1 \leq i \leq N$ și $l \leq j \leq r$ vor produce cu $val$ mai multe mere.
• 3 i j K → Interogare: Dacă Gigel ar porni din celula $(i, j)$ și s-ar lăsa purtat de vânt prin matrice timp de exact $K$ secunde, câte mere ar colecta în total? Gigel va colecta inclusiv merele din celula din care începe, așadar el va colecta de fapt merele din $K + 1$ celule. Deoarece acest număr poate fi foarte mare, se cere restul împărțirii lui la $2^{32}$. Atenție! Dacă Gigel părăsește matricea la orice moment de timp pe parcursul zborului, acesta se încheie definitiv, iar răspunsul interogării se va considera $-1$.

Cerință

Să se răspundă corect la toate interogările asociate evenimentelor de tipul 3.

Date de intrare

Pe prima linie se află numerele $N$, $M$ și $Q$, separate prin câte un spațiu. Pe următoarele $N$ linii se vor regăsi $M$ caractere $d$, neseparate de spații, reprezentând direcțiile inițiale ale vântului din fiecare celulă din matrice. Fiecare dintre următoarele $Q$ linii descrie câte un eveniment, în formatul de mai sus.

Date de ieșire

Se va afișa pe câte o linie răspunsul la fiecare interogare asociată unui eveniment de tip 3.

Restricții și precizări

• $1 \leq N \leq 25$;
• $1 \leq M \leq 50 \ 000$;
• $1 \leq Q \leq 100 \ 000$;
• $1 \leq K \leq 10^9$;
• $1 \leq val \leq 10^9$;
• $d \in \{$N, S, E, V$\}$;
• $1 \leq i \leq N$ și $1 \leq j \leq M$ pentru toate evenimentele de tipurile 1 și 3;
• $1 \leq l \leq r \leq M$ pentru toate evenimentele de tipul 2;
• Liniile și coloanele sunt indexate de la 1;
• Interogările se consideră pe matricele curente de la pasul respectiv, ele nu se schimbă în timp ce Gigel este purtat de vânt.

Exemplul 1

wind.in

2 6 6
EEESES
NEEENE
3 1 1 9
3 1 2 5
2 3 4 10
3 1 3 4
1 2 4 V
3 1 2 5

wind.out

-1
35
63
88

Explicație

În continuare explicăm primul exemplu.

Starea Inițială

Datele de intrare specifică $N = 2$, $M = 6$ și $Q = 6$. Matricea inițială a merelor $A_0$ se calculează cu formula $a[i][j] = (i - 1) \cdot M + j$:

Matricea inițială a direcțiilor vântului $D_0$ este preluată direct din datele de intrare:

Evenimentul 1: 3 1 1 9

Tipul 3: Interogare traseu pornind din $(1, 1)$ timp de $K = 9$ secunde.

Traseul și Merele Colectate:

Explicație: După 9 secunde, Gigel părăsește matricea prin Est. Zborul se încheie.

Rezultat afișat: $-1$

Evenimentul 2: 3 1 2 5

Tipul 3: Interogare traseu pornind din $(1, 2)$ timp de $K = 5$ secunde.

Traseul și Merele Colectate:

Total Mere: $2 + 3 + 4 + 10 + 11 + 5 = \mathbf{35}$

Evenimentul 3: 2 3 4 10

Tipul 2: Se adaugă câte $10$ mere în toate celulele de pe coloanele $3$ și $4$.

Matricea Merelor Actualizată $A_1$:

Evenimentul 4: 3 1 3 4

Tipul 3: Interogare traseu pornind din $(1, 3)$ timp de $K = 4$ secunde.

Traseul și Merele Colectate:

Total Mere: $13 + 14 + 20 + 11 + 5 = \mathbf{63}$

Evenimentul 5: 1 2 4 V

Tipul 1: Se schimbă direcția vântului în celula $(2, 4)$ în Vest (V).

Matricea Direcțiilor Actualizată $D_1$:

Evenimentul 6: 3 1 2 5

Tipul 3: Interogare traseu pornind din $(1, 2)$ timp de $K = 5$ secunde.

Traseul și Merele Colectate:

Total Mere: $2 + 13 + 14 + 20 + 19 + 20 = \mathbf{88}$

Exemplul 2

wind.in

3 4 10
EESV
NVES
EENN
3 1 1 2
3 1 1 1000000000
1 2 4 V
3 1 1 100
2 3 4 10
3 1 1 100
1 2 3 N
3 1 1 10
1 1 3 N
3 1 1 5

wind.out

6
1410065389
741
1731
136
-1