J - Rotate and Reverse Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

問題文

N 行 N 列のマス目があります。最初は全てのマスが白く塗られています。

Q 個のクエリ \text{Query}_1,\text{Query}_2,\ldots,\text{Query}_Q が与えられるので、順に処理してください。

クエリには 3 種類あり、入力形式とクエリの内容は以下の通りです。

  • 1 x y : 上から x 行目、左から y 列目のマスが白なら黒く、黒なら白く塗り替える。
  • 2 c : グリッド全体を、c が A なら時計回りに、B なら反時計回りに 90 度回す。
  • 3 c : グリッド全体を、c が A なら上下反転、B なら左右反転させる。

全てのクエリを処理した後のマス目の状態を求めてください。

制約

  • 1 \leq N \leq 300
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq x,y \leq N
  • c は A、B のいずれか
  • 各クエリは問題文中の 3 種類のいずれか

入力

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

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

出力

N 行出力せよ。

i\,(1 \leq i \leq N) 行目には、0 と 1 のみからなる長さ N の文字列 S を出力せよ。S の j 文字目は、最終的なマス目の上から i 行目、左から j 列目のマスの色を表し、0 は白、1 は黒に対応する。

入力例 1

3 2
1 1 1
2 A

出力例 1

001
000
000

上から 1 行目、左から 1 列目のマスを黒く塗り替えた後、グリッド全体を時計回りに 90 度回転させます。

入力例 2

3 3
1 1 1
3 A
3 B

出力例 2

000
000
001

入力例 3

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

出力例 3

0000
0000
0100
0000

Score : 6 points

Problem Statement

We have a grid with N rows and N columns. Initially, all squares are painted white.

Process Q queries \text{Query}_1,\text{Query}_2,\ldots,\text{Query}_Q in the order they are given.

There are three kinds of queries, with the following input formats and specifications.

  • 1 x y : If the square at the x-th row from the top and y-th column from the left is white, repaint it black; if it is black, repaint it white.

  • 2 c : Rotate the whole grid 90 degrees clockwise if c is A and counter-clockwise if c is B.

  • 3 c : Flip the whole grid vertically if c is A and horizontally if c is B.

Find the colors of the squares after processing all queries.

Constraints

  • 1 \leq N \leq 300
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq x,y \leq N
  • c is A or B.
  • Each query is of one of the three kinds described in Problem Statement.

Input

Input is given from Standard Input in the following format:

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

Output

Print N lines.

The i-th line (1 \leq i \leq N) should contain a string of length N consisting of 0 and 1, where the j-th character of S represents the color of the square at the i-th row from the top and j-th column from the left in the final grid; use 0 for white and 1 for black.

Sample Input 1

3 2
1 1 1
2 A

Sample Output 1

001
000
000

We repaint the square at the 1-st row from the top and 1-st column from the left and then rotate the whole grid 90 degrees clockwise.

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