题目描述

小 C 学会了一种数组操作：她会在一个 $n \times n$ 的二维方阵上，将某个奇数阶子方阵按顺时针或逆时针旋转 $90^\circ$。

初始时，小 C 把 $1$ 到 $n^2$ 按从左到右、从上到下的顺序填入方阵。然后她会依次执行若干次旋转操作。

请你输出所有操作执行完毕后的最终方阵。

输入格式

第一行两个整数 $n, m$，分别表示方阵大小和操作次数。

接下来 $m$ 行，每行 $4$ 个整数 $x, y, r, z$，表示将第 $x$ 行第 $y$ 列为中心、边长为 $2r+1$ 的子方阵旋转。$z = 0$ 表示顺时针旋转 $90^\circ$，$z = 1$ 表示逆时针旋转 $90^\circ$。

输出格式

输出 $n$ 行，每行 $n$ 个用空格隔开的整数，表示最终的方阵。

样例

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

提示

对于 $50\%$ 的数据，$r = 1$；

对于 $100\%$ 的数据，$1 \leq n, m \leq 500$，$1 \leq x - r \leq x + r \leq n$，$1 \leq y - r \leq y + r \leq n$。