题目描述

$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$

输入格式

入力は以下の形式で標準入力から与えられる。

$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$ 個目の質問に対する答えを整数として出力せよ。

题目大意

给定一个 $N\times M$ 的矩阵 $A$，有

$$A_{i,j}= \begin{cases} (i-1)M+j&((i+j)\bmod 2=0) \\ 0&((i+j)\bmod 2=1) \end{cases} $$

给定 $Q$ 次询问，每次询问给出 $X_1,X_2,Y_1,Y_2$。求以 $(X_1,Y_1)$ $(X_2,Y_2)$ 为左上角和右下角的矩形的元素之和。对 $998244353$ 取模。

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

28
27
36
14
0
104

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

716070898
240994972
536839100

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

712559605
648737448
540261130

提示

制約

• 入力は全て整数
• $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$

Sample Explanation 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$ です。

Sample Explanation 2

$1$ 個目の質問について、マス $(10^9,10^9)$ に書かれている整数は $10^{18}$ ですが、それを $998244353$ で割った余りを求めることに注意してください。