← 返回题目列表

Codeforces · 341/D

D. Iahub 和 Xors

中文机器翻译题面 查看原题

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。