회전

$N \times N$ 크기의 정사각형 보드가 있다. 보드는 $N$행 $N$열의 칸으로 이루어져 있으며, 위에서 $i$번째, 왼쪽에서 $j$번째 칸을 $(i, j)$라고 한다. 칸 $(i, j)$에는 문자 $A_{ij}$가 적혀 있다.

보드의 정사각형 영역 하나를 시계 반대 방향으로 90도 회전하는 작업을 $Q$번 반복한다. $k$번째 회전은 $(I_k, J_k)$ 칸을 왼쪽 위 모서리로 포함하는 $S_k \times S_k$ 크기의 정사각형 영역을 회전한다.

모든 회전을 마친 최종 보드를 구하라.

첫 번째 줄에 정수 $N$과 $Q$가 공백으로 구분되어 주어진다. $N$은 보드의 크기, $Q$는 회전 횟수이다.

이어서 $N$개의 줄에 보드의 초기 상태가 주어진다. $i$번째 줄의 $j$번째 문자가 $A_{ij}$이다. 문자열은 소문자 알파벳으로만 이루어져 있다.

이어서 $Q$개의 줄에 회전 정보가 주어진다. $k$번째 줄에는 정수 $I_k$, $J_k$, $S_k$가 공백으로 구분되어 주어진다. 이는 $k$번째 회전이 $(I_k, J_k)$ 칸을 왼쪽 위 모서리로 포함하는 $S_k \times 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$이다.

최종 보드를 $N$줄에 걸쳐 출력한다. $i$번째 줄에는 $N$개의 문자로 이루어진 문자열을 출력하며, 그 $j$번째 문자가 최종 보드의 $(i, j)$ 칸에 적힌 문자이다.

• $2 \le N \le 1000$ (보드의 크기)
• $1 \le Q \le 2000$ (회전 횟수)