CF405C.Unusual Product

Little Chris is a huge fan of linear algebra. This time he has been given a homework about the unusual square of a square matrix.

The dot product of two integer number vectors x and y of size n is the sum of the products of the corresponding components of the vectors. The unusual square of an n × n square matrix A is defined as the sum of n dot products. The i-th of them is the dot product of the i-th row vector and the i-th column vector in the matrix A.

Fortunately for Chris, he has to work only in GF(2)! This means that all operations (addition, multiplication) are calculated modulo 2. In fact, the matrix A is binary: each element of A is either 0 or 1. For example, consider the following matrix A:

The unusual square of A is equal to (1·1 + 1·0 + 1·1) + (0·1 + 1·1 + 1·0) + (1·1 + 0·1 + 0·0) = 0 + 1 + 1 = 0.

However, there is much more to the homework. Chris has to process q queries; each query can be one of the following:

1. given a row index i, flip all the values in the i-th row in A;
2. given a column index i, flip all the values in the i-th column in A;
3. find the unusual square of A.

To flip a bit value w means to change it to 1 - w, i.e., 1 changes to 0 and 0 changes to 1.

Given the initial matrix A, output the answers for each query of the third type! Can you solve Chris's homework?

小 Chris 非常热爱线性代数。这一次，他被布置了一道关于方阵“非同寻常的平方”（unusual square）的作业题。

两个长度为 $n$ 的整数向量 $x$ 和 $y$ 的点积（dot product），定义为它们对应分量乘积之和。一个 $n \times n$ 方阵 $A$ 的非同寻常的平方定义为 $n$ 个点积之和；其中第 $i$ 项是矩阵 $A$ 的第 $i$ 行向量与第 $i$ 列向量的点积。

幸运的是，Chris 只需在二元域 $GF(2)$ 中运算！这意味着所有运算（加法、乘法）均对 $2$ 取模。事实上，矩阵 $A$ 是二进制的：其每个元素非 $0$ 即 $1$。例如，考虑如下矩阵 $A$：

$A$ 的非同寻常的平方等于

$$(1\cdot1 + 1\cdot0 + 1\cdot1) + (0\cdot1 + 1\cdot1 + 1\cdot0) + (1\cdot1 + 0\cdot1 + 0\cdot0) = 0 + 1 + 1 = 0.$$

然而，这份作业远不止于此。Chris 还需要处理 $q$ 个查询；每个查询属于以下三种类型之一：

1. 给定行索引 $i$，将矩阵 $A$ 的第 $i$ 行所有值翻转（flip）；
2. 给定列索引 $i$，将矩阵 $A$ 的第 $i$ 列所有值翻转（flip）；
3. 求矩阵 $A$ 的非同寻常的平方。

所谓翻转（flip）一个比特值 $w$，即将其变为 $1 - w$：$1$ 变为 $0$，$0$ 变为 $1$。

给定初始矩阵 $A$，请输出所有第 3 类查询所对应的答案！你能帮 Chris 完成这份作业吗？

The first line of input contains an integer n (1 ≤ n ≤ 1000), the number of rows and the number of columns in the matrix A. The next n lines describe the matrix: the i-th line contains n space-separated bits and describes the i-th row of A. The j-th number of the i-th line a__ij (0 ≤ a__ij ≤ 1) is the element on the intersection of the i-th row and the j-th column of A.

The next line of input contains an integer q (1 ≤ q ≤ 106), the number of queries. Each of the next q lines describes a single query, which can be one of the following:

• 1 i — flip the values of the i-th row;
• 2 i — flip the values of the i-th column;
• 3 — output the unusual square of A.

Note: since the size of the input and output could be very large, don't use slow output techniques in your language. For example, do not use input and output streams (cin, cout) in C++.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 1000$），表示矩阵 $A$ 的行数与列数。接下来的 $n$ 行描述该矩阵：第 $i$ 行包含 $n$ 个以空格分隔的比特位，表示矩阵 $A$ 的第 $i$ 行。第 $i$ 行中的第 $j$ 个数 $a_{ij}$（$0 \leq a_{ij} \leq 1$）是矩阵 $A$ 中第 $i$ 行与第 $j$ 列交点处的元素。

输入的下一行包含一个整数 $q$（$1 \leq q \leq 10^6$），表示查询的数量。接下来的 $q$ 行每行描述一个查询，查询类型如下：

• 1 i — 翻转第 $i$ 行的所有值；
• 2 i — 翻转第 $i$ 列的所有值；
• 3 — 输出矩阵 $A$ 的“非同寻常平方”（unusual square）。

注意：由于输入和输出的数据量可能非常大，请勿在程序中使用低效的输入/输出方式。例如，在 C++ 中请勿使用 cin 和 cout。

Let the number of the 3rd type queries in the input be m. Output a single string s of length m, where the i-th symbol of s is the value of the unusual square of A for the i-th query of the 3rd type as it appears in the input.

设输入中第 3 类查询的数量为 $m$。输出一个长度为 $m$ 的字符串 $s$，其中 $s$ 的第 $i$ 个字符为输入中第 $i$ 个第 3 类查询所对应的矩阵 $A$ 的“特殊平方”值。