Problem Description

There is a grid of $ N $ rows and $ N $ columns. Initially, all cells are painted white.

You are given $ Q $ queries $\text{Query}_1, \text{Query}_2, \ldots, \text{Query}_Q$. Process them in order.

There are three types of queries, with the following input format and content:

• 1 x y: If the cell at the $ x $-th row from the top and $ y $-th column from the left is white, paint it black; if it is black, paint it white.
• 2 c: Rotate the entire grid $ 90 $ degrees clockwise if $ c $ is A, and counterclockwise if $ c $ is B.
• 3 c: Invert the entire grid vertically if $ c $ is A, and horizontally if $ c $ is B.

Determine the state of the grid after processing all queries.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $\text{Query}_1$ $\text{Query}_2$ $\vdots$ $\text{Query}_Q$

Output Format

Output $ N $ lines.

On the $i\,(1 \leq i \leq N)$-th line, output a string $ S $ of length $ N $ consisting only of 0 and 1. The $ j $-th character of $ S $ represents the color of the cell at the $ i $-th row from the top and $ j $-th column from the left in the final grid, where 0 corresponds to white and 1 corresponds to black.

Sample Input and Output

Sample Input #1

3 2
1 1 1
2 A

Sample Output #1

001
000
000

Sample Input #2

3 3
1 1 1
3 A
3 B

Sample Output #2

000
000
001

Sample Input #3

4 8
2 A
1 4 2
2 A
1 2 2
3 B
3 B
3 A
1 3 1

Sample Output #3

0000
0000
0100
0000

Notes/Hints

Constraints

• $1 \leq N \leq 300$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq x, y \leq N$
• $ c $ is either A or B
• Each query is one of the three types described in the problem statement

Sample Explanation 1

After painting the cell at the $ 1 $-st row and $ 1 $-st column black, rotate the entire grid $ 90 $ degrees clockwise.

见题面 Input 部分

见题面 Output 部分