有一个 $N \times N$ 的方格盘面，其中填满了 $N \times N$ 个方格。我们将从上往下第 $i$ 行、从左往右第 $j$ 列的方格称为方格 $(i, j)$。方格 $(i, j)$ 中写有字符 $A_{ij}$。

你需要对某个正方形区域进行 $Q$ 次逆时针 90 度旋转。第 $k$ 次旋转操作会旋转一个包含 $S_k \times S_k$ 个方格的正方形区域，该区域以方格 $(I_k, J_k)$ 为左上角。

请计算并输出最终的盘面。

数据范围

$2 \le N \le 1000$ 盘面大小 $1 \le Q \le 2000$ 旋转次数

输入格式

从标准输入读取以下内容：

• 第一行包含两个整数 $N$ 和 $Q$，以空格分隔。$N$ 表示盘面大小，$Q$ 表示旋转次数。
• 接下来的 $N$ 行给出了盘面初始的字符。第 $i$ 行包含一个长度为 $N$ 的字符串，该字符串的第 $j$ 个字符表示 $A_{ij}$。字符串仅包含小写英文字母。
• 接下来的 $Q$ 行给出了旋转指令。第 $k$ 行包含三个整数 $I_k, J_k, S_k$ ($1 \le I_k \le N - S_k + 1, 1 \le J_k \le N - S_k + 1, 2 \le S_k \le N$)，以空格分隔。这表示第 $k$ 次旋转操作会旋转以方格 $(I_k, J_k)$ 为左上角的 $S_k \times S_k$ 正方形区域。

输出格式

将最终的盘面输出到标准输出，共 $N$ 行。即第 $i$ 行输出一个长度为 $N$ 的字符串，其第 $j$ 个字符为最终盘面中 $(i, j)$ 位置的字符。

子任务

在所有测试数据中，有 10% 的分值满足 $N \le 100, Q \le 100$。

样例

输入 1

4 1
abcd
efgh
ijkl
mnop
2 2 2

输出 1

abcd
egkh
ifjl
mnop

说明

该输入表示如下盘面：

abcd
efgh
ijkl
mnop

第 1 次旋转指令为“旋转以方格 $(2, 2)$ 为左上角的 $2 \times 2$ 正方形区域”。即，将：

fg
jk

逆时针旋转 90 度，得到：

abcd
egkh
ifjl
mnop