Problem B: Matrix Operations

Problem

要素が1と0からなるn×nの行列に対して、以下の種類の操作を行うプログラムを作成せよ。

部分行列と角度(0,90,180,270,360)が与えられるのでその分だけ時計回りに回転させる。

部分行列が与えられるので値を反転させる。

行が与えられるので左に1個シフトし、はみ出た分は右端に移動する。

行が与えられるので右に１個シフトし、はみ出た分は左端に移動する。

行(r),列(c)が与えられる。
Step1：現在のセルを(r,c)にする。
Step2：現在のセルの値を反転する。
Step3：隣接するセルのうち、値が現在のセルの反転前の値と等しいセルに対し、Step2とStep3の処理を行う。
ここで、セル(i,j)に隣接するセルとは、(i-1,j), (i+1,j),(i,j-1),(i,j+1)の４つである。

Input

n m
a1,1 a1,2 ... a1,n
a2,1 a2,2 ... a2,n
:
an,1 an,2 ... an,n
Operation1
Operation2
:
Operationm

入力の最初に2つの整数nとmが空白区切りで与えられる。 nは行列のサイズ、mは操作の数を表している。

次にグリッドの情報がn行で与えられ、グリッドの情報のi行目にはn個の整数 a_i,jが空白区切りで与えられる。a_i,jには0か1が与えられる。

次に1行で表される各Operation_iがm個与えられる。 Operation_i の最初の入力はo(操作の種類)が入力される。

oが0のときは回転(Rotate)を表している。 続く入力は、r c size angle(行、列、サイズ、角度) が空白区切りで与えられる。 左上(r,c)から右下(r+size-1,c+size-1)が部分行列となる。 正方行列になることは保証されている。

oが1のときは反転(Reversal)を表している。 また、続く入力は、r c size (行、列、サイズ) が空白区切りで与えられる。 左上(r,c)から右下(r+size-1,c+size-1)が部分行列となる。 正方行列になることは保証されている。

oが2のときは左シフト(Left shift)を表している。 また、続く入力は r(行) が与えられる。

oが3のときは右シフト(Right shift)を表している。 また、続く入力は r(行) が与えられる。

oが4のときは島反転(Island reversal)を表している。 また、続く入力は r c(行、列) が空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

• 1 ≤ n,r,c,size ≤ 15
• 1 ≤ m ≤ 100
• 0 ≤ o ≤ 4
• 1 ≤ r+size-1,c+size-1 ≤ 15
• 0 ≤ angle ≤ 360

Output

生成された行列を出力して下さい。

Sample Input 1

3 1
1 1 0
0 1 1
1 0 1
0 2 2 2 90

Sample Output 1

1 1 0
0 0 1
1 1 1

Sample Input 2

5 2
0 0 0 0 0
1 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
3 2
4 2 2

Sample Output 2

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

Sample Input 3

5 2
1 1 1 0 1
1 0 0 0 0
0 0 0 1 1
0 1 0 0 0
0 1 1 1 0
1 3 3 3
0 1 1 5 90

Sample Output 3

0 0 0 1 1
1 1 0 0 1
0 1 1 0 1
0 1 0 0 0
1 1 0 0 1