P2117 Xiao Z's Matrix

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$.

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 a single line consisting of several numbers with no spaces, representing the result of each operation (no output for operations 1 and 2).

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