実行時間制限: 3 sec / メモリ制限: 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