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 \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 翻译