Description

Xiao Z has recently become obsessed with matrices. He defines a characteristic function $G$ for a special kind of matrix. For an $N \times N$ matrix $A$ where every element of $A$ is $0$ or $1$, define $\displaystyle G(A) = \left(\sum_{i = 1}^n\sum_{j = 1}^n A_{i, j}\cdot A_{j, i}\right) \bmod 2$. For example:

$$\begin{pmatrix} 1 & 1 & 1\\ 0 & 1 & 1\\ 1 & 0 & 0\\ \end{pmatrix}$$

For the $3 \times 3$ matrix $A$ above, $G(A)=(1\times 1+1\times 0+1\times 1+0\times 1+1\times 1+1\times 0+1\times 1+ 0\times 1+0\times 0) \bmod 2 = 0$.

Of course, querying the $G$ value of a single matrix is too simple. Along with giving you an $N \times N$ matrix, Xiao Z also gives you $Q$ operations, described as follows:

• Operation 1: of the form 1 x, which means “flip” all elements in row $x$.
• Operation 2: of the form 2 x, which means “flip” all elements in column $x$.
• Operation 3: an integer 3, which asks for the current value of the characteristic function $G$.

“Flip” means changing $1$ to $0$ and $0$ to $1$.

Input Format

The first line contains two positive integers $N, Q$. $N$ is the number of rows (and columns) of the matrix, and $Q$ is the number of operations.

The next $N$ lines describe an $N \times N$ matrix $A$, with $0 \le A_{i, j} \le 1$.

The next $Q$ lines contain the $Q$ operations.

Output Format

Output a single line consisting of several numbers with no spaces, representing the result of each operation (no output for operations 1 and 2).

3 12
1 1 1
0 1 1
1 0 0
3
2 3
3
2 2
2 2
1 3
3
3
1 2
2 1
1 1
3

01001

Hint

Constraints

• For $30\%$ of the testdata, $N \le 100$, $Q \le 10^5$.
• For $100\%$ of the testdata, $N \le 1{,}000$, $Q \le 5 \times 10^5$.

Translated by ChatGPT 5