Problem Description

Scarlet has recently learned an array magic. On an $n \times n$ 2D array, she can rotate an odd-order square submatrix by $90^\circ$ clockwise or counterclockwise.

First, Scarlet fills the initial 2D array with the positive integers from $1$ to $n^2$ in order from left to right and from top to bottom, and then she casts some simple magic.

Scarlet does not know any block decomposition tricks, nor any Splay-on-Splay. She now gives you the order in which she performs her magic, and she wants you to tell her what the 2D array looks like after all the operations are performed in order.

Input Format

The first line contains two integers $n, m$, representing the size of the square matrix and the number of magic operations.

The next $m$ lines each contain $4$ integers $x, y, r, z$, meaning that in this operation, Scarlet rotates the $(2r+1)$-order matrix centered at row $x$, column $y$ by $90^\circ$ in a certain direction, where $z=0$ means clockwise and $z=1$ means counterclockwise.

Output Format

Output $n$ lines, each containing $n$ numbers separated by spaces, representing the final matrix.

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

5 10 3 18 15
4 19 8 17 20
1 14 23 24 25
6 9 2 7 22
11 12 13 16 21

Hint

For $50\%$ of the testdata, $r=1$.

For $100\%$ of the testdata, $1 \leq n, m \leq 500$, $1 \leq x-r \leq x+r \leq n$, $1 \leq y-r \leq y+r \leq n$.

Translated by ChatGPT 5