17772번 - Rotate 다국어

문제

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

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

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

입력

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

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

출력

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

제한

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

힌트