Matrix Characteristic Function and Flip Operations

Given an N × N matrix A whose elements are either 0 or 1, define the characteristic function G as:

$$ G(A)=\left(\sum_{i=1}^{N}\sum_{j=1}^{N} A_{i,j}\cdot A_{j,i}\right) \bmod 2 $$

You are also given Q operations. The operations are defined as follows:

• Operation 1: 1 x — Flip (invert) all elements in row x (i.e. change 0 to 1 and 1 to 0).
• Operation 2: 2 x — Flip (invert) all elements in column x.
• Operation 3: 3 — Query the current value of G(A).

Note: The matrix indices are considered to be 1-indexed.

inputFormat

The first line of input contains two integers N and Q representing the dimensions of the matrix and the number of operations, respectively.

The next N lines each contain N integers (each either 0 or 1) representing the initial state of the matrix A.

Then, Q lines follow, each representing an operation in one of the following forms:

• 1 x: Flip all elements in row x.
• 2 x: Flip all elements in column x.
• 3: Query the current characteristic value G(A), where $$ G(A)=\left(\sum_{i=1}^{N}\sum_{j=1}^{N} A_{i,j}\cdot A_{j,i}\right) \bmod 2. $$

outputFormat

For each query operation (operation 3), output the current value of G(A) on a separate line.

sample

3 4
1 1 1
0 1 1
1 0 0
3
1 2
2 1
3

0
0