Jungol

N \cdot N 크기의 정사각형 격자판이 하나 있다. 이 격자판의 각 칸에는 알파벳 소문자가 하나씩 써있다.

준혁이는 이 격자판을 Q번 돌리면서 놀 생각이었다.

준혁이는 Q번의 회전중 i번째로 판을 돌릴 때, X_i행 Y_i열의 칸을 가장 왼쪽 위로 하고 크기가 S_i \cdot S_i인 부분 정사각형을 뽑아 반시계방향으로 통째로 90도를 회전시켜 다시 집어 넣을 계획이다.

하지만 준혁이는 갑자기 판을 돌리기 귀찮아졌다. 그렇지만 결과는 여전히 궁금하기 때문에 여러분이 모든 회전이 끝난 판의 모양을 계산해주자.

입력

첫 줄에 N, Q가 공백을 사이에 두고 주어진다. (2\le N\le 1000, 1\le Q\le 2000)

이후 N줄에 처음 격자판의 상태가 주어진다.

이후 Q줄에 걸쳐 i번째 줄에 X_i, Y_i, S_i가 공백을 사이에 두고 주어진다.

출력

Q번의 회전을 모두 실행한 후 최종 판의 상태를 출력하라.

예제1

예제2

태그

출처

JOI spring camp 2011/2012

회전 2000초 1024MB