#10827. 矩阵异或和

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: admin

题目描述

在一个 N×M 的矩阵 A 中,第 i 行,第 j 列的数字为 A[i][j]。小明询问小途 q 个问题,对于每个问题,小明会告诉小途四个整数 x_1,y_1,x_2,y_2,小途需要回答出左上角为 (x_1,y_1),右下角为 (x_2,y_2)的矩阵中所有数的异或和。

异或和是指多个数进行连续异或的结果,例如:ans = a ^ b ^ c; 其中 a,b,c 均为变量。

输入格式

输入第一行是以空格隔开的两个正整数 N,M,表示矩阵的大小。

接下来 N 行,每行有 M 个以空格隔开的非负整数,表示矩阵 A。

接下来一行一个正整数 q,表示小明共有 q 次询问。

接下来 q 行,每行四个正整数 x_1,y_1,x_2,y_2,表示小明询问的矩阵的左上角为 (x_1,y_1),右下角为 (x_2,y_2)。

输出格式

输出共 q 行,每行一个非负整数,表示小明询问的矩阵内所有数字的异或和。

样例

样例输入

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
1
1 2 3 4

样例输出

12

数据范围与提示

对于 30% 的数据,1≤N,M≤100,1≤q≤100; 对于 100% 的数据,1≤N,M≤1000,1≤q≤10^5,0≤A[i][j]≤10^9,1≤x_1≤x_2≤N,1≤y_1≤y_2≤M;