分数: 500 点
问题陈述
我们有一个网格 N 行和 M 列。广场 (i,j) 在 i从顶部开始的第行和 j左起第 列有一个整数 (i-1) \times M + j 。
让我们在此网格上执行以下操作。
- 对于每个方格 (i,j) 这样 i+j 是奇数,将该方格上的整数替换为 0.
答案 Q 操作后在格上提问。
的 i第一个问题如下:
- 求所有方格上写的整数之和 (p,q) 满足以下所有条件,模 998244353.
- A_i \le p \le B_i.
- C_i \le q \le D_i.
约束
- 输入中的所有值都是整数。
- 1 \le N,M \le 10^9
- 1 \le Q \le 2 \times 10^5
- 1 \le A_i \le B_i \le N
- 1 \le C_i \le D_i \le 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
此输入中的网格如下所示。

此输入包含六个问题。
- 第一个问题的答案是 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
对于第一个问题,请注意,虽然正方形上写的是整数 (10^9,10^9) is 10^{18},你要找到它的模 998244353.
示例输入 3
999999999 999999999 3 999999999 999999999 999999999 999999999 216499784 840031647 84657913 415448790 1 999999999 1 999999999
示例输出 3
712559605 648737448 540261130