Rotate

There is a board of $N \times N$ cells arranged in $N$ rows and $N$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is called cell $(i, j)$. Cell $(i, j)$ contains the letter $A_{ij}$.

Rotate a square region 90 degrees counterclockwise, repeating this operation $Q$ times. The $k$-th rotation takes the $S_k \times S_k$ square region whose top-left cell is $(I_k, J_k)$ and rotates it.

Find the final board.

The first line contains integers $N$ and $Q$, separated by a space. $N$ is the board size and $Q$ is the number of rotations.

The next $N$ lines give the initial board. The $j$-th character of the $i$-th line is $A_{ij}$. Each string contains only lowercase English letters.

The next $Q$ lines give the rotations. The $k$-th line contains integers $I_k$, $J_k$, and $S_k$, separated by spaces. This means the $k$-th rotation takes the $S_k \times S_k$ square region whose top-left cell is $(I_k, J_k)$ and rotates it. Here $1 \le I_k \le N - S_k + 1$, $1 \le J_k \le N - S_k + 1$, and $2 \le S_k \le N$.

Print the final board in $N$ lines. The $i$-th line is a string of $N$ characters, whose $j$-th character is the letter in cell $(i, j)$ of the final board.

• $2 \le N \le 1000$ (board size)
• $1 \le Q \le 2000$ (number of rotations)