#P17615. Xor Matrix

Xor Matrix

题目描述

给出一个 n×mn\times m 的矩阵,第 ii 行第 jj 列填着 (i−1)m+j(i-1)m+j。

求以 (x,y)(x,y) 为左上角,(z,w)(z,w) 为右下角的子矩阵的 kk 进制下异或和(即不进位加法,比如九进制下 (45)9 xor (87)9=(33)9(45)_9\ \mathrm{xor}\ (87)_9=(33)_9)。

输入格式

为了减小测试点个数,本题单个测试点内有多个询问。时间限制已经根据询问组数作了相应调整。

第一行两个正整数 n,mn,m。

接下来一行一个整数 qq,表示询问次数。

接下来 qq 行,每行五个正整数 x,y,z,w,kx,y,z,w,k,表示一次询问。

输出格式

输出 qq 行,每行一个整数,表示询问的答案。

输入输出样例 #1

输入 #1

15 233
2
1 1 3 3 2
4 8 14 200 24

输出 #1

319
7032

输入输出样例 #2

输入 #2

939 943 
10
94 618 848 927 92
421 16 525 45 99
77 524 662 779 82
316 630 910 669 51
857 241 890 447 9
44 30 95 409 83
408 302 804 331 73
571 42 761 334 70
419 220 704 855 54
432 80 669 799 52

输出 #2

33786429
97803
41147634
6638925
738
96232
19796958
14611599
6717042
6402992

说明/提示

本题捆绑测试。

对于所有数据,1≤n,m≤nm≤10101\le n,m\le nm\le 10^{10},1≤q≤101\le q\le 10,1≤x≤z≤n1\le x\le z\le n,1≤y≤w≤m1\le y\le w\le m,2≤k≤1092\le k\le 10^9。

详细数据范围如下表:

Subtask 编号 nmnm 特殊性质 分数
11 ≤1010\le 10^{10} n≤105n\le 10^5 1818
22 ≤2×109\le 2\times 10^{9} 无 6161
33 ≤1010\le 10^{10} 2121