← 返回题目列表

AtCoder · abc269_f

I. 编号检查器

中文机器翻译题面 查看原题

分数: 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