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 matricei sunt egale cu 0. Asupra matricei A se va efectua o succesiune de M operații, de următoarele tipuri:

• 1 i1 j1 i2 j2 X – se adaugă valoarea X tuturor elementelor din submatricea cu colțul stânga-sus în (i1, j1) și colțul dreapta-jos în (i2, j2). Cu alte cuvinte, toate elementele Ai,j cu i1 ≤ i ≤ i2 și j1 ≤ j ≤ j2 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ța

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 ≤ N ≤ 1.500
• 1 ≤ M ≤ 100.000
• 1 ≤ X, K ≤ 1.000.000.000
• Toate numerele din fișierul de intrare sunt naturale.
• Datorită dimensiunilor mari, nu au fost adăugate toate testele.

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