Rotate(回転) - joi2012-day2
時間制限: 2秒
メモリ制限: 64MB
課題
正方形のマスが縦 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 | 出力例1 |
|---|---|
| 4 1 abcd efgh ijkl mnop 2 2 2 |
abcd egkh ifjl mnop |
この入力は下のような盤面を表す．
abcd efgh ijkl mnop
1 つ目の回転の指示は，「マス (2, 2) を最も左上のマスとして含む 2 \times 2 個のマスを含む正方形領域を回転する」というものである．つまり，
fg jk
を反時計回りに 90 度回転させ，
abcd egkh ifjl mnop
を得る．