P7819 [RC-05] Xor Matrix

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$).

**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 $q$ lines. Each line contains one integer, the answer to the corresponding query.

**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 ID | $nm$ | Special Property | Score | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $\le 10^{10}$ | $n\le 10^5$ | $18$ | | $2$ | $\le 2\times 10^{9}$ | None | $61$ | | $3$ | $\le 10^{10}$ | None | $21$ | ### 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