rotate - 回転 Editorial /

Time Limit: 2 sec / Memory Limit: 64 MiB

配点 : 100 点

問題文

課題

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

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

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

制約

  • 2 \leqq N \leqq 1\,000:盤面のサイズ.
  • 1 \leqq Q \leqq 2\,000:回転の回数.

入力

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

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

出力

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

採点基準

採点用データのうち,配点の 10\% 分については,N \leqq 100,Q \leqq 100 を満たす.

入出力の例

入力例 1

4 1
abcd
efgh
ijkl
mnop
2 2 2

出力例 1

abcd
egkh
ifjl
mnop

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

abcd
efgh
ijkl
mnop

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

fg
jk

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

abcd
egkh
ifjl
mnop

を得る.


Source Name

JOI 2011-2012 春季トレーニング合宿 Contest Day2