Description

You are given an $n\times m$ matrix. The value in row $i$ and column $j$ is $(i-1)m+j$.

For each query, compute the base-$k$ xor sum of the submatrix with top-left corner $(x,y)$ and bottom-right corner $(z,w)$ (that is, addition without carry. For example, in base $9$, $(45)_9\ \mathrm{xor}\ (87)_9=(33)_9$).

Input Format

To reduce the number of test points, this problem contains multiple queries in a single test. The time limit has been adjusted according to the number of query groups.

The first line contains two positive integers $n,m$.

The next line contains an integer $q$, the number of queries.

The next $q$ lines each contain five positive integers $x,y,z,w,k$, describing one query.

Output Format

Output $q$ lines. Each line contains one integer, the answer to the corresponding query.

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

Hint

This problem uses bundled judging.

For all data, $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$.

The detailed Constraints are shown in the table below:

Subtask Dependencies

On Luogu, this problem does not have subtask dependencies. On InfOJ, subtask $3$ depends on subtask $1$. During final scoring, the version with subtask dependencies will be used.

Translated by ChatGPT 5