Costin are o matrice pătratică $A$ cu $N$ linii (numerotate de sus în jos de la $1$ la $N$) și $N$ coloane (numerotate de la stânga la dreapta de la $1$ la $N$). Inițial toate elementele matricii sunt egale cu $0$. Asupra matricii $A$ se va efectua o succesiune de $M$ operații, de următoarele tipuri:

• $1 \ i_1 \ j_1 \ i_2 \ j_2 \ X$ - se adaugă valoarea $X$ tuturor elementelor din submatricea cu colțul stânga-sus în $(i_1, j_1)$ și colțul dreapta-jos în $(i_2, j_2)$. Cu alte cuvinte, toate elementele $A_{i,j}$ cu $i_1 \leq i \leq i_2$ și $j_1 \leq j \leq j_2$ se adună cu $X$.
• $2 \ K$ - matricea se va roti de $K$ ori cu $90$ de grade spre stânga (vezi fig. 1, pentru $K = 1$).
• $3$ - flip orizontal (prima linie devine ultima linie, a doua devine penultima ș.a.m.d. vezi fig. 2)
• $4$ - flip vertical (prima coloană va deveni ultima coloană, a doua va deveni penultima, ș.a.m.d. - vezi fig. 3)

Cerință

Scrieți un program care, cunoscând $N$, precum și o succesiune de $M$ operații, afișează matricea rezultată în urma efectuării în ordine a operațiilor din succesiune.

Date de intrare

Fișierul de intrare matrix.in conține pe prima linie numărul $N$, pe a doua linie numărul $M$, iar pe următoarele $M$ linii cele $M$ operații din succesiune, în forma descrisă în enunț, câte o operație pe o linie.

Date de ieșire

Fișierul de ieșire matrix.out va conține $N$ linii, pe fiecare dintre acestea aflându-se $N$ numere separate prin spațiu, ce descriu matricea rezultată după efectuarea operațiilor.

Restricții și precizări

• $1 \leq N \leq 1 \ 500$
• $1 \leq M \leq 100 \ 000$
• $1 \leq X, K \leq 1 \ 000 \ 000 \ 000$
• Toate numerele din fișierul de intrare sunt naturale.

Exemplu

matrix.in

3 5
1 2 2 3 3 2
2 2
1 1 2 3 3 1
3
4

matrix.out

1 1 0
1 3 2
1 3 2