小Z的矩阵

题目描述

小Z最近迷上了矩阵，他定义了一个对于一种特殊矩阵的特征函数 $G$。对于 $N\times N$ 的矩阵 $A$，$A$ 的所有元素均为 $0$ 或 $1$，则 $G(A) = \left(\sum\limits_{i = 1}^n\sum\limits_{j = 1}^n A_{i, j}\cdot A_{j, i}\right) \bmod 2$。举一个例子：

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

对于上面这个 $3\times 3$ 矩阵 $A$，$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$。

当然询问一个矩阵的 $G$ 值实在是太简单了。小Z在给出一个 $N\times N$ 矩阵的同时将给你 $Q$ 个操作，操作描述如下：

操作1：形如 1 x，表示将第 $x$ 行的元素全部“翻转”。

操作2：形如 2 x，表示将第 $x$ 列的元素全部“翻转”。

操作3：形如一个整数 3，表示询问当前矩阵的特征值 $G$。

“翻转”的定义为将 $1$ 变成 $0$，将 $0$ 变成 $1$。

输入格式

第 $1$ 行：两个正整数 $N,Q$。$N$ 表示矩阵的行数（列数），$Q$ 表示询问的次数。

接下来 $N$ 行：一个 $N\times N$ 的矩阵 $A$，$0\le A_{i, j}\le 1$。

接下来 $Q$ 行：$Q$ 个操作。

输出格式

一行若干个数，中间没有空格，分别表示每个操作的结果（操作 $1$ 和操作 $2$ 不需要输出）。

提示

【数据规模】

• 对于 $30\%$ 的数据，$N\le 100, Q\le 10^5$

• 对于 $100\%$ 的数据，$N\le 1,000, Q \le 5\times 10^5$