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