题目描述

本题使用文件输入输出：输入文件名为 diag.in，输出文件名为 diag.out。

一个 $n$ 行 $m$ 列的表格，行从上到下编号 $1 \sim n$，列从左到右编号 $1 \sim m$。小 Z 要把 $1 \sim n \times m$ 这些数沿斜线填进表格里。

把第 $x$ 行第 $y$ 列的格子记作 $(x, y)$，它所在的斜线编号是 $x+y$。填数的顺序是：

• 先填斜线 $2$ 上的格子（只有 $(1,1)$），再填斜线 $3$ 上的格子，再填斜线 $4$ 上的格子……直到斜线 $n+m$；
• 同一条斜线上有若干个格子，如果斜线编号是偶数，就按行号从小到大的顺序填；如果是奇数，就按行号从大到小的顺序填。

例如 $n = 3$，$m = 4$ 时，填好的表格是：

$$\begin{array}{cccc} 1 & 3 & 4 & 9 \\ 2 & 5 & 8 & 10 \\ 6 & 7 & 11 & 12 \end{array}$$

现在有 $q$ 次询问，每次给出一个格子 $(x, y)$，请你回答这个格子里填的数。

输入格式

输入文件名为 diag.in。

第一行三个整数 $n, m, q$，表示表格的行数、列数和询问次数。

接下来 $q$ 行，每行两个整数 $x, y$，表示询问格子 $(x, y)$ 里填的数。

输出格式

输出文件名为 diag.out。

共 $q$ 行，每行一个整数，依次回答每个询问。

样例 #1

样例输入 #1

3 4 5
1 1
2 2
3 2
1 4
3 4

样例输出 #1

1
5
7
9
12

样例解释

对照题目描述里的表格。以 $(3,2)$ 为例：它在斜线 $5$ 上，斜线 $2,3,4$ 共有 $1+2+3=6$ 个格子，所以斜线 $5$ 从 $7$ 开始填；斜线 $5$ 是奇数，按行号从大到小填，$(3,2)$ 的行号最大、排第一个，所以填 $7$。

样例 #2

样例输入 #2

4 2 4
4 2
3 1
2 2
4 1

样例输出 #2

8
5
4
6

样例解释

$n = 4$，$m = 2$ 时表格是：

$$\begin{array}{cc} 1 & 3 \\ 2 & 4 \\ 5 & 7 \\ 6 & 8 \end{array}$$

提示

数据范围

• 对于 $30\%$ 的数据：$n, m \le 100$；
• 对于 $60\%$ 的数据：$n, m \le 2000$；
• 对于 $100\%$ 的数据：$1 \le n, m \le 10^5$，$1 \le q \le 10^5$，$1 \le x \le n$，$1 \le y \le m$。