問題文

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

制約

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

入力例 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

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

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

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

出力例 2

716070898
240994972
536839100

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

入力例 3

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

出力例 3

712559605
648737448
540261130