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

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

この入力では、グリッドは以下の通りです。

この入力には $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$ です。

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

716070898
240994972
536839100

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

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

712559605
648737448
540261130