Tricky Matrix Updates

Cerință

Se dă o matrice cu $N$ linii și $M$ coloane, inițial plină cu zero-uri. Se vor efectua $Q$ operații de două tipuri:

• SUS col l1 l2 val
• JOS col l1 l2 val

O operație de tip SUS adaugă valoarea $val$ pe o fâșie verticală de lungime $l2-l1+1$ începând de la linia $l1$ până la linia $l2$ pe coloana $col$. Pentru fiecare coloană din dreapta, fâșia se deplasează cu o unitate în sus (adică pe coloana $col+1$ fâșia va fi de la $l1-1$ la $l2-1$, pe $col+2$ de la $l1-2$ la $l2-2$ etc.), până când fâșia nu mai încape în matrice.

O operație de tip JOS adaugă valoarea $val$ pe o fâșie verticală de lungime $l2-l1+1$ începând de la linia $l1$ până la linia $l2$ pe coloana $col$. Pentru fiecare coloană din dreapta, fâșia se deplasează cu o unitate în jos (adică pe coloana $col+1$ fâșia va fi de la $l1+1$ la $l2+1$, pe $col+2$ de la $l1+2$ la $l2+2$ etc.), până când fâșia nu mai încape în matrice.

După efectuarea tuturor operațiilor, se cere să se afișeze matricea rezultată.

Date de intrare

Prima linie conține trei numere întregi $N$, $M$, $Q$ — dimensiunile matricei și numărul de operații.

Urmează $Q$ linii, fiecare descriind o operație de forma:

• S col l1 l2 val sau
• J col l1 l2 val

Date de ieșire

Se va afișa matricea rezultată, fiecare linie pe câte un rând, elementele separate prin spațiu.

Restricții

• $1 \leq N, M \leq 1000$
• $1 \leq Q \leq 2*10^6$
• $1 \leq col \leq M$
• $1 \leq l1 \leq l2 \leq N$
• $1 \leq val \leq 10^9$

Subtask-uri

• Subtask 1 (20 puncte): $N, M, Q \leq 100$
• Subtask 2 (35 puncte): $N, M \leq 500$, $Q \leq 100\,000$
• Subtask 3 (45 puncte): $N, M \leq 1000$, $Q \leq 2\,000\,000$

Exemplu

stdin

5 5 1
S 1 3 5 1

stdout

0 0 1 1 1
0 1 1 1 0
1 1 1 0 0
1 1 0 0 0
1 0 0 0 0

stdin

4 4 2
S 2 2 4 2
J 1 1 2 3

stdout

3 0 2 2 
3 5 2 2 
0 5 5 0 
0 2 3 3