There is a board with $N \times N$ square cells, arranged in $N$ rows and $N$ columns. We call the cell at the $i$-th row from the top and $j$-th column from the left as cell $(i, j)$. The character $A_{ij}$ is written in cell $(i, j)$.
We repeat a counter-clockwise 90-degree rotation of a certain square region $Q$ times. The $k$-th rotation rotates the square region of size $S_k \times S_k$ that includes cell $(I_k, J_k)$ as its top-left cell.
Find and output the final state of the board.
Constraints
- $2 \le N \le 1000$ (Size of the board)
- $1 \le Q \le 2000$ (Number of rotations)
Input
Read the following from standard input:
- The first line contains two integers $N$ and $Q$ separated by a space. $N$ represents the size of the board, and $Q$ represents the number of rotations.
- The following $N$ lines provide the characters initially written on the board. The $i$-th line contains a string of length $N$. The $j$-th character of this string represents $A_{ij}$. The strings contain only lowercase English letters.
- The following $Q$ lines contain the rotation instructions. The $k$-th line contains three integers $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$) separated by spaces. This indicates that the $k$-th rotation rotates the square region of size $S_k \times S_k$ that includes cell $(I_k, J_k)$ as its top-left cell.
Output
Output the final board in $N$ lines to standard output. That is, output $N$ lines, where the $i$-th line is a string of length $N$ whose $j$-th character is the character written in cell $(i, j)$ of the final board.
Subtasks
For 10% of the test cases, $N \le 100$ and $Q \le 100$ are satisfied.
Examples
Input 1
4 1 abcd efgh ijkl mnop 2 2 2
Output 1
abcd egkh ifjl mnop
Note
This input represents the following board:
abcd efgh ijkl mnop
The first rotation instruction is "rotate the $2 \times 2$ square region that includes cell $(2, 2)$ as its top-left cell." That is, we rotate:
fg jk
counter-clockwise by 90 degrees, to obtain:
abcd egkh ifjl mnop