小克里斯是线性代数的超级粉丝。这次他的作业是关于方阵中不寻常的平方。
大小为 n 的两个整数向量 x 和 y 的点积是向量相应分量的乘积之和。 n × n 方阵 A 的异常方定义为 n 点积之和。其中第i个是矩阵A中第i个行向量和第i个列向量的点积。
克里斯幸运的是,他只需要在 GF(2) 中工作!这意味着所有运算(加法、乘法)均以模 2 计算。事实上,矩阵 A 是二进制的:A 的每个元素不是 0 就是 1。例如,考虑以下矩阵 A:
A 的异常平方等于 (1·1 + 1·0 + 1·1) + (0·1 + 1·1 + 1·0) + (1·1 + 0·1 + 0·0) = 0 + 1 + 1 = 0。
然而,作业还有很多。 Chris 必须处理 q 个查询;每个查询可以是以下之一:
1. 给定行索引 i,翻转 A 中第 i 行的所有值;
2.给定一个列索引i,翻转A中第i列的所有值;
3. 求 A 的异常平方。
翻转一个位值 w 意味着将其变为 1 - w,即 1 变为 0,0 变为 1。
给定初始矩阵A,输出第三种类型的每个查询的答案!你能解决克里斯的作业吗?
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 1000)、矩阵 A 的行数和列数。接下来的 n 行描述矩阵:第 i 行包含 n 个空格分隔的位,描述 A 的第 i 行。第 i 行的第 j 个数字 aij (0 ≤ aij ≤ 1) 是第 i 行与A 的第 j 列。
下一行输入包含一个整数 q (1 ≤ q ≤ 106),即查询次数。接下来的 q 行中的每一行都描述一个查询,可以是以下查询之一:
- 1 i — 翻转第 i 行的值;
- 2 i — 翻转第 i 列的值;
- 3 — 输出 A 的异常平方。
注意:由于输入和输出的大小可能非常大,因此请勿在您的语言中使用慢速输出技术。例如,不要在 C++ 中使用输入和输出流(cin、cout)。
输出
设输入中的第三类查询的数量为m。输出长度为 m 的单个字符串 s,其中 s 的第 i 个符号是输入中出现的第三类型第 i 个查询的 A 的异常平方值。
示例
输入 #1
3 1 1 1 0 1 1 1 0 0 12 3 2 3 3 2 2 2 2 1 3 3 3 1 2 2 1 1 1 3
输出 #1
01001