题目描述

我们有一个N行M列的网格。网格中的$(i,j)$方格代表着从上到下第i行，从左到右第j列的方格，上面写着一个整数$(i-1) \times M + j$。

对于这个网格，我们进行以下操作：

• 对于所有满足$i+j$为奇数的$(i,j)$方格，将该方格上的整数替换为0。

对网格进行了这个操作之后，回答Q个关于网格的问题。第i个问题如下：

• 求出满足以下条件的所有方格$(p,q)$上整数的和，对$998244353$取模：
  • $A_i \leq p \leq B_i$
  • $C_i \leq q \leq D_i$

约束条件

• 输入中的所有值都是整数。
• $1 \leq N, M \leq 10^9$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq A_i \leq B_i \leq N$
• $1 \leq C_i \leq D_i \leq M$

输入和输出

输入以以下格式从标准输入给出：

$N\ M$ $Q$ $A_1\ B_1\ C_1\ D_1$ $A_2\ B_2\ C_2\ D_2$ $\vdots$ $A_Q\ B_Q\ C_Q\ D_Q$

输出应为$Q$行。第$i$行应为第$i$个问题的答案。

样例

样例输入1

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

样例输出1

28
27
36
14
0
104

样例解释1

该样例中的网格如下所示：

0  2  0  4
1  0  3  0
0  6  0  8
5  0  7  0
0 10  0 11

共有六个问题。

• 第一个问题的答案是$0+3+0+6+0+8+0+11+0=28$。
• 第二个问题的答案是$1+0+9+0+17=27$。
• 第三个问题的答案是$17+0+19+0=36$。
• 第四个问题的答案是$14$。
• 第五个问题的答案是$0$。
• 第六个问题的答案是$104$。

样例输入2

1000000000 1000000000
3
1000000000 1000000000 1000000000 1000000000
165997482 306594988 719483261 992306147
1 1000000000 1 1000000000

样例输出2

716070898
240994972
536839100

样例解释2

对于第一个问题，需要注意的是尽管方格$(10^9,10^9)$上的整数为$10^{18}$，但要对$998244353$取模。

样例输入3

999999999 999999999
3
999999999 999999999 999999999 999999999
216499784 840031647 84657913 415448790
1 999999999 1 999999999

样例输出3

712559605
648737448
540261130

样例解释3

这个样例与样例2类似。