Rotating Photo

PCK is developing an application for processing photos by rotating them. In this application, a square photo is input, and then the photo is rotated by several rotation commands, each of which rotates the photo 90 degrees clockwise or counterclockwise around a point in the middle of the photo (the intersection of the diagonals of the square).

Given a photo and a rotation instruction, write a program that draws the photo after processing all the instructions. The photo consists of $N \times N$ pixels, and the information of one pixel is represented by a single letter.

Input

The input is given in the following format.

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

The first line gives the number of pixels in the photo $N$ ($1 \leq N \leq 1,000$), in both height and width. In the following $N$ lines, the pixel information $row_i$ of the $i$-th row from the top is given, where $row_i$ is a string of length $N$ consisting of letters. The next line gives the number of rotation instructions $Q$ ($1 \leq Q \leq 200,000$). In the following line $Q$, an integer $r_i$ (-1 or 1) is given to indicate the direction of rotation; a value of $r_i$ of 1 means clockwise rotation, and a value of -1 means counterclockwise rotation by 90 degrees.

Output

Output the pixel information of the photo after processing all the rotation commands in $N$ lines. The pixel information of the $i$-th row from the top is output to the $i$-th row.    

Sample Input and Output

Sample Input 1

2
AI
ZU
2
1
1

Sample Output 1

UZ
IA

Sample Input 2

3
xOO
OOy
OOO
1
-1	

Sample Output 2

OyO
OOO
xOO

---