No testdata at current.

AT_abc269_f [ABC269F] Numbered Checker

题目描述

有一个 $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$

输入格式

输入以如下格式从标准输入读入。

$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

输入 #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

输入输出样例 #2

输入 #2

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

输出 #2

716070898
240994972
536839100

输入输出样例 #3

输入 #3

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

输出 #3

712559605
648737448
540261130

说明/提示

数据范围

• 输入均为整数。
• $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$

样例解释 1

在本输入中，网格如下所示。
本输入包含 $6$ 个询问。

• 第 $1$ 个询问的答案为 $0+3+0+6+0+8+0+11+0=28$。
• 第 $2$ 个询问的答案为 $1+0+9+0+17=27$。
• 第 $3$ 个询问的答案为 $17+0+19+0=36$。
• 第 $4$ 个询问的答案为 $14$。
• 第 $5$ 个询问的答案为 $0$。
• 第 $6$ 个询问的答案为 $104$。

样例解释 2

对于第 $1$ 个询问，格子 $(10^9,10^9)$ 上写着的整数是 $10^{18}$，但需要对 $998244353$ 取模。

由 ChatGPT 4.1 翻译