题目描述

有一个$n \times n$的方阵，现将 1 到 $n^2$ 按照从左往右，从上至下的顺序填入初始的二维数组中。

然后需要完成一系列操作，具体地说每一个操作可以表示为将二维数组上将一个$(2r + 1) × (2r + 1)$的子矩阵按照顺时针或者逆时针旋转90度(详见输入格式)。

需要输出经过一系列操作后的矩阵。

输入格式

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

接下来 $m$ 行，每行 4 个整数 $x$, $y$, $r$, $z$，该次操作会把以第 $x$ 行第 y 列为中心的$(2r + 1) × (2r + 1)$的子矩阵按照某种时针方向旋转。其中 z = 0 表示顺时针，z = 1 表示逆时针。

输出格式

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

样例

5 1
2 2 1 0

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

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

数据范围

本题共有10个测试点。

对于$20\%$的数据，满足 $r = 1$。

对于另外$40\%$的数据，满足 $1 ≤ n, m ≤ 10$。

对于$100\%$的数据 $1 ≤ n, m ≤ 500$，满足 $1 ≤ x − r ≤ x + r ≤ n, 1 ≤ y − r ≤ y + r ≤ n$。