题目描述
给出一个 $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$ 行，每行一个整数，表示询问的答案。
样例
样例输入 1
15 233 2 1 1 3 3 2 4 8 14 200 24
样例输出 1
319 7032
样例输入 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\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$。
详细数据范围如下表：
| Subtask 编号 | $nm$ | 特殊性质 | 分数 |
|---|---|---|---|
| $1$ | $\le 10^{10}$ | $n\le 10^5$ | $18$ |
| $2$ | $\le 2\times 10^{9}$ | 无 | $61$ |
| $3$ | $\le 10^{10}$ | 无 | $21$ |
子任务依赖
本题中，子任务 $3$ 依赖于子任务 $1$。（即，如果没有通过子任务 $1$，就不会评测子任务 $3$）