题目描述

给出一个 $n\times m$ 的矩阵，第 $i$ 行第 $j$ 列填着 $(i-1)m+j$。

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

输入格式

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

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

接下来一行一个整数 $q$，表示询问次数。

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

输出格式

输出 $q$ 行，每行一个整数，表示询问的答案。

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

319
7032

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

33786429
97803
41147634
6638925
738
96232
19796958
14611599
6717042
6402992

提示

本题捆绑测试。

对于所有数据，$1\le n,m\le nm\le 10^{10}$，$1\le q\le 10$，$1\le x\le z\le n$，$1\le y\le w\le m$，$2\le k\le 10^9$。

详细数据范围如下表：

子任务依赖

在洛谷上，本题没有设置子任务依赖。在 InfOJ 上，子任务 $3$ 依赖于子任务 $1$。最终评分时，按照存在子任务依赖的版本评分。