AT_abc269_f [ABC269F] Numbered Checker

[problemUrl]: https://atcoder.jp/contests/abc269/tasks/abc269_f $ 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 $

N/A

N/A

### 制約 - 入力は全て整数 - $ 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 $ ### Sample Explanation 1 この入力では、グリッドは以下の通りです。 !\[\](https://img.atcoder.jp/abc269/81d92debe7aa949266f3a00cff13b513.png) この入力には $ 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 $ です。 ### Sample Explanation 2 $ 1 $ 個目の質問について、マス $ (10^9,10^9) $ に書かれている整数は $ 10^{18} $ ですが、それを $ 998244353 $ で割った余りを求めることに注意してください。