Rotate

正方形のマスが縦 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 回転の回数