F - Numbered Checker Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 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

制約

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

Score : 500 points

Problem Statement

We have a grid with N rows and M columns. The square (i,j) at the i-th row from the top and j-th column from the left has an integer (i-1) \times M + j written on it.
Let us perform the following operation on this grid.

  • For every square (i,j) such that i+j is odd, replace the integer on that square with 0.

Answer Q questions on the grid after the operation.
The i-th question is as follows:

  • Find the sum of the integers written on all squares (p,q) that satisfy all of the following conditions, modulo 998244353.
    • A_i \le p \le B_i.
    • C_i \le q \le D_i.

Constraints

  • All values in the input are integers.
  • 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

Input

The input is given from Standard Input in the following format:

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

Output

Print Q lines.
The i-th line should contain the answer to the i-th question as an integer.

Sample Input 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

Sample Output 1

28
27
36
14
0
104

The grid in this input is shown below.

This input contains six questions.

  • The answer to the first question is 0+3+0+6+0+8+0+11+0=28.
  • The answer to the second question is 1+0+9+0+17=27.
  • The answer to the third question is 17+0+19+0=36.
  • The answer to the fourth question is 14.
  • The answer to the fifth question is 0.
  • The answer to the sixth question is 104.

Sample Input 2

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

Sample Output 2

716070898
240994972
536839100

For the first question, note that although the integer written on the square (10^9,10^9) is 10^{18}, you are to find it modulo 998244353.

Sample Input 3

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

Sample Output 3

712559605
648737448
540261130