Iahub 不喜欢背景故事,所以他会准确地告诉你这个问题要求你做什么。
给定一个 n 行 n 列的矩阵 a。最初,矩阵的所有值均为零。行和列均从 1 开始,即行编号为 1, 2, ..., n,列编号为 1, 2, ..., n。我们将第 i 行第 j 列上的元素表示为 ai, j。
我们将这样的元素 ai, j 称为子矩阵 (x0, y0, x1, y1),其中两个不等式成立:x0 ≤ i ≤ x1, y0 ≤ j ≤ y1。
编写一个程序来执行以下两个操作:
1. 查询(x0, y0, x1, y1):打印子矩阵(x0, y0, x1, y1)元素的异或和。
2. Update(x0, y0, x1, y1, v):子矩阵 (x0, y0, x1, y1) 中的每个元素通过值 v 进行异或运算。
输入
第一行包含两个整数:n (1 ≤ n ≤ 1000) 和 m (1 ≤ m ≤ 105)。数字 m 代表您需要执行的操作数。接下来的 m 行中的每一行包含五个或六个整数,具体取决于操作类型。
如果输入的第 i 个操作是查询,则第 i 行的第一个数字将为 1。后面将跟着四个整数 x0、y0、x1、y1。如果第 i 个操作是更新,则第 i 行的第一个数字将为 2。后面将跟着五个整数 x0、y0、x1、y1、v。
保证对于每个更新操作,以下不等式成立:0 ≤ v < 262。保证对于每个操作,以下不等式成立:1 ≤ x0 ≤ x1 ≤ n,1 ≤ y0 ≤ y1 ≤ n。
输出
对于每个查询操作,在新行中输出结果。
示例
输入 #1
3 5 2 1 1 2 2 1 2 1 3 2 3 2 2 3 1 3 3 3 1 2 2 3 3 1 2 2 3 2
输出 #1
3 2
注意
前 3 次运算后,矩阵将如下所示:
第四个运算要求我们计算 1 xor 2 xor 3 xor 3 = 3。
第五个运算要求我们计算 1 xor 3 = 2。