时间限制：1000ms　内存限制：512MB

题目描述

程老师有一面拼图墙，由 $n \times n$ 块瓷砖拼成。每块瓷砖上印着一个编号，从上到下、从左到右排成一个方阵。

程老师有一种独特的拧砖手法。他会先在墙上选定一块 $k \times k$ 的正方形区域——只需要说出这个区域左上角所在的行号和列号，再加上边长 $k$，就能唯一确定要拧哪块。然后，他把这 $k \times k$ 块瓷砖当作一个整体，顺时针旋转 90 度。

具体来说，旋转前左上角的那块瓷砖会跑到右上角去，右上角的跑到右下角，右下角的跑到左下角，左下角的跑到左上角。其余瓷砖也按照同样的规律转动，整个子方阵就像一个被拧了一下的拼图块。

这个手法可以反复使用。程老师一共拧了 $m$ 次，每次选定的区域可以不同，大小也可以不同，每一次操作都是基于当前墙面的状态进行的。

现在，请你根据初始墙面和程老师的 $m$ 次操作，输出最终的墙面状态。

输入格式

第一行两个整数 $n, m$，分别表示墙面的边长和操作次数。

接下来 $n$ 行，每行 $n$ 个整数，表示初始墙面。第 $i$ 行第 $j$ 个数表示第 $i$ 行第 $j$ 列瓷砖上的编号。

接下来 $m$ 行，每行三个整数 $x, y, k$，表示一次操作：选定左上角在第 $x$ 行第 $y$ 列、边长为 $k$ 的子方阵，将其顺时针旋转 90 度。

输出格式

输出 $n$ 行，每行 $n$ 个整数，表示最终的墙面。同一行的整数之间用一个空格隔开。

数据范围

• 特殊性质 A：所有操作的 $k = 1$。
• 特殊性质 B：所有操作的 $x = y = 1$ 且 $k = n$。
• 瓷砖编号为不超过 $10^9$ 的正整数。
• 保证 $1 \le x \le n - k + 1$，$1 \le y \le n - k + 1$，即选定的子方阵不会超出墙面范围。

样例

样例 1

输入：

3 2
1 2 3
4 5 6
7 8 9
1 1 2
2 2 2

输出：

4 1 3
5 8 2
7 9 6

样例 2

输入：

2 1
1 2
3 4
1 1 1

输出：

1 2
3 4

样例 3

输入：

2 1
1 2
3 4
1 1 2

输出：

3 1
4 2

样例解释

样例 1： 第一次操作选定左上角（行 1 列 1）、边长 2 的子方阵，即 1、2、4、5 四块瓷砖。顺时针旋转后，1 转到右上角（原来 2 的位置），2 转到右下角（原来 5 的位置），5 转到左下角（原来 4 的位置），4 转到左上角（原来 1 的位置）。墙面变为：

4 1 3
5 2 6
7 8 9

第二次操作选定左上角（行 2 列 2）、边长 2 的子方阵，即 2、6、5、8。顺时针旋转后，墙面变为：

4 1 3
5 8 2
7 9 6

样例 2： 唯一的操作边长为 1。墙面没有任何变化，输出和输入相同。

样例 3： 整面墙（$2 \times 2$）被顺时针旋转。左上角的 1 转到右上角，右上角的 2 转到右下角，右下角的 4 转到左下角，左下角的 3 转到左上角。最终墙面为：

3 1
4 2