Numbered Checker

AtCoder

IDabc269_f

Time3000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

Output #1

28
27
36
14
0
104

The grid in this input is shown below.  
![image](https://img.atcoder.jp/abc269/81d92debe7aa949266f3a00cff13b513.png)
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$.

Input #2

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

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

Input #3

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

Output #3

712559605
648737448
540261130

API Response (JSON)

{
  "problem": {
    "name": "Numbered Checker",
    "description": {
      "content": "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 th",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc269_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.  \nLet us perform th...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments