题目描述

在一个N×M的矩阵A中，第i行，第j列的数字为A[i][j]。询问q个问题，对于每个问题有四个整数x1，y1，x2，y2。你需要回答出左上角为(x1, y1)，右下角为(x2, y2)的矩阵中所有数的异或和。

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

对于N=4，M=5的矩阵，如果x1=1，y1=2，x2=3，y2=4，那么表示的矩阵如下图中红色部分。

输入格式

第一行是以空格隔开的两个正整数N，M(1≤N, M≤1000)，表示矩阵的大小；

接下来N行，每行有M个以空格隔开的，不大于1000的非负整数，表示矩阵A；

接下来一行一个正整数q(1≤q≤10^5)，表示共有q次询问；

接下来q行，每行四个正整数x1，y1，x2，y2(1≤x1≤x2≤N, 1≤y1≤y2≤M)，表示询问的矩阵左上角为(x1, y1)，右下角为(x2, y2)。

输出格式

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

输入/输出样例

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

12
2

说明/提示

时间1000ms，内存256MiB