题目描述

小 Z 最近迷上了矩阵，他定义了一个对于一种特殊矩阵的特征函数 $G$。对于 $N\times N$ 的矩阵 $A$，$A$ 的所有元素均为 $0$ 或 $1$，则 $\displaystyle G(A) = \left(\sum_{i = 1}^n\sum_{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$。

输入格式

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

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

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

输出格式

一行若干个数，中间没有空格，分别表示每个操作的结果（操作 1 和操作 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

提示

【数据规模】

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

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