#P2117. 小Z的矩阵

小Z的矩阵

题目描述

小 Z 最近迷上了矩阵,他定义了一个对于一种特殊矩阵的特征函数 GG。对于 N×NN\times N 的矩阵 AAAA 的所有元素均为 0011,则 $\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×33\times 3 矩阵 AA,$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$。

当然询问一个矩阵的 GG 值实在是太简单了。小Z在给出一个 N×NN\times N 矩阵的同时将给你 QQ 个操作,操作描述如下:

  • 操作 1:形如 1 x,表示将第 xx 行的元素全部“翻转”。
  • 操作 2:形如 2 x,表示将第 xx 列的元素全部“翻转”。
  • 操作 3:形如一个整数3,表示询问当前矩阵的特征值 GG

“翻转”的定义为将 11 变成 00,将 00 变成 11

输入格式

第一行:两个正整数 N,QN,QNN 表示矩阵的行数(列数),QQ 表示询问的次数。

接下来 NN 行:一个 N×NN\times N 的矩阵 AA0Ai,j10\le A_{i, j}\le 1

接下来 QQ 行:QQ 个操作。

输出格式

一行若干个数,中间没有空格,分别表示每个操作的结果(操作 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%30\% 的数据,N100N\le 100Q105Q\le 10^5

  • 对于 100%100\% 的数据,N1,000N\le 1,000Q5×105Q \le 5\times 10^5