Bobo 有一个 $n$ 行 $n$ 列的矩阵。行从上到下编号为 $0, 1, \dots, (n - 1)$，列从左到右编号为 $0, 1, \dots, (n - 1)$。位于第 $i$ 行第 $j$ 列的单元格记作 $(i, j)$。每个单元格 $(i, j)$ 中初始填写的数字为 $i \times n + j$。

Bobo 将依次进行 $q$ 次变换。变换共有 2 种类型。第 $i$ 次变换的类型为 $t_i$，由 3 个参数 $l_i, r_i, d_i$ 描述。

如果 $t_i = 1$，则对于 $l_i \le x \le r_i$ 且 $0 \le y < n$ 的单元格，变换会将单元格 $(x, (y + d_i) \pmod n)$ 中的数字转移到单元格 $(x, y)$。

如果 $t_i = 2$，则对于 $0 \le x < n$ 且 $l_i \le y \le r_i$ 的单元格，变换会将单元格 $((x + d_i) \pmod n, y)$ 中的数字转移到单元格 $(x, y)$。

注意 $a \pmod b$ 表示 $a$ 除以 $b$ 的余数。

Bobo 想知道矩阵最终的状态。

输入格式

第一行包含 2 个整数 $n, q$ ($1 \le n \le 200, 1 \le q \le 10^5$)。

接下来的 $q$ 行，第 $i$ 行包含 4 个整数 $t_i, l_i, r_i, d_i$ ($t_i \in \{1, 2\}, 0 \le l_i \le r_i < n, 0 \le d_i < n$)。

输出格式

输出 $n$ 行。第 $i$ 行包含 $n$ 个整数 $a_{i,0}, a_{i,1}, \dots, a_{i,n-1}$，表示最终单元格 $(i, j)$ 中的数字。

样例

样例输入 1

3 2
1 1 1 1
2 1 1 1

样例输出 1

0 5 2
4 7 3
6 1 8

样例输入 2

3 1
1 0 2 1

样例输出 2

1 2 0
4 5 3
7 8 6