写真の回転

PCK君は、写真を回転して加工するアプリケーションを開発しています。このアプリケーションでは、正方形の写真を１つ入力した後、複数の回転命令によって写真を回転させます。１つの回転命令で、写真の真ん中の点(正方形の対角線の交点)を軸として時計回りまたは反時計回りに90°回転させます。

写真と回転命令が与えられたとき、すべての命令を処理した後の写真を描画するプログラムを作成せよ。ただし、写真はN×N個のピクセルで構成され、１つのピクセルの情報は英文字１つで表すものとする。

入力

入力は以下の形式で与えられる。

$N$
$row_1$
$row_2$
:
$row_N$
$Q$
$r_1$
$r_2$
:
$r_Q$

１行目に写真の縦と横のピクセルの数$N$ ($1 \leq N \leq 1,000$)が与えられる。続く$N$行に上から$i$番目にある行のピクセル情報$row_i$が与えられる。$row_i$は英文字からなる長さ$N$の文字列である。続く1行に回転命令の数$Q$ ($1 \leq Q \leq 200,000$)が与えられる。続く$Q$行に、回転の方向を表す整数$r_i$ (-1 または 1)が与えられる。$r_i$が1のとき時計回りに、-1のとき反時計回りに90°回転することを意味する。

出力

すべての回転命令を処理した後の写真のピクセル情報をN行に出力する。上から$i$番目にある行のピクセル情報を$i$行目に出力する。  

入出力例

入力例１

2
AI
ZU
2
1
1

出力例１

UZ
IA

入力例２

3
xOO
OOy
OOO
1
-1	

出力例２

OyO
OOO
xOO

Note

Algorithm

 

---