005 - 写真の回転

時間制限 1 秒 / メモリ制限 256 MB / 得点 20 / x 9 /


TLE
1sec
MLE
256MB
得点
20

問題文

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

課題

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

入力

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

$N$
$roe_{1}$
$roe_{2}$
$\vdots$
$roe_{N}$
$Q$
$r_{1}$
$r_{2}$
$\vdots$
$r_{Q}$

1行目に写真の縦と横のピクセルの数$N\ (1 \leq N \leq 1000)$が与えられる。続く$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^{\circ}$回転することを意味する。

出力

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

入出力例

入力例1

2
AI
ZU
2
1
1

出力例1

UZ
IA

入力例2

3
xOO
OOy
OOO
1
-1

出力例2

OyO
OOO
xOO