시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

正方形のマスが縦 N 行,横 N 列に N × N 個敷き詰められている盤面がある.上から i 番目,左から j 番 目のマスをマス (i, j) と呼ぶ.マス (i, j) には文字 Aij が書かれている.

ある正方形領域を反時計回りに 90 度回転させることを Q 回繰り返す.k 回目の回転は,マス (Ik, Jk) を 最も左上のマスとして含む Sk × Sk 個のマスを含む正方形領域を回転する.

最終的な盤面を求め出力せよ.

입력

標準入力から以下の入力を読み込め.

  • 1 行目には整数 N, Q が空白を区切りとして書かれている.N は盤面のサイズを,Q は回転の回数を 表す.
  • 続く N 行には,盤面に最初に書かれている文字が与えられる.これらの行の i 行目には長さ N の文 字列が書かれている.この文字列の j 文字目は Aij を表す.文字列はアルファベットの小文字のみを 含む.
  • 続く Q 行には,回転の指示が書かれている.これらの行の k 行目には整数 Ik, Jk, Sk (1 ≤ Ik ≤ N − Sk + 1, 1 ≤ Jk ≤ N − Sk + 1, 2 ≤ Sk ≤ N) が空白を区切りとして書かれている.これは, k 回目の回転はマス (Ik, Jk) を最も左上のマスとして含む Sk × Sk 個のマスを含む正方形領域を回転す ることを表す.

출력

標準出力に,最終的な盤面を N 行で出力せよ.すなわち,i 行目に,N 文字の文字列であって,j 番目の 文字が最終的な盤面の (i, j) に書かれている文字となっているものを出力せよ.

제한

  • 2 ≤ N ≤ 1 000 盤面のサイズ
  • 1 ≤ Q ≤ 2 000 回転の回数

예제 입력 1

4 1
abcd
efgh
ijkl
mnop
2 2 2

예제 출력 1

abcd
egkh
ifjl
mnop

この入力は下のような盤面を表す.

abcd
efgh
ijkl
mnop

1 つ目の回転の指示は,「マス (2, 2) を最も左上のマスとして含む 2 × 2 個のマスを含む正方形領域を回転 する」というものである.つまり,

fg
jk

を反時計回りに 90 度回転させ,

abcd
egkh
ifjl
mnop

を得る.