AT_abc255_h [ABC255Ex] Range Harvest Query

[problemUrl]: https://atcoder.jp/contests/abc255/tasks/abc255_h $ N $ 本の木があります。$ 0 $ 日目にはどの木にも実は一つもなっていません。 $ 1 $ 日目以降の毎朝、それぞれの $ i\ =\ 1,\ 2,\ \ldots,\ N $ について、$ i $ 番目の木に $ i $ 個の実が増えます。 高橋君は $ Q $ 回の収穫作業をします。 $ i\ =\ 1,\ 2,\ \ldots,\ Q $ について、$ i $ 回目の収穫作業は $ D_i $ 日目の夜に行われ、その時点で $ L_i $ 番目から $ R_i $ 番目の木になっているすべての実を収穫します。 $ Q $ 回の収穫作業のそれぞれについて、高橋君が収穫する実の個数を $ 998244353 $ で割ったあまりを出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ D_1 $ $ L_1 $ $ R_1 $ $ D_2 $ $ L_2 $ $ R_2 $ $ \vdots $ $ D_Q $ $ L_Q $ $ R_Q $

$ Q $ 行出力せよ。 $ i\ =\ 1,\ 2,\ \ldots,\ Q $ について、$ i $ 行目には高橋君が $ i $ 回目の収穫作業で収穫する実の個数を $ 998244353 $ で割ったあまりを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 10^{18} $ - $ 1\ \leq\ Q\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ D_1\ \lt\ D_2\ \lt\ \cdots\ \lt\ D_Q\ \leq\ 10^{18} $ - $ 1\ \leq\ L_i\ \leq\ R_i\ \leq\ N $ - 入力はすべて整数 ### Sample Explanation 1 $ i\ =\ 1,\ 2,\ 3,\ 4,\ 5 $ について、$ i $ 番目の木になっている実の個数を $ A_i $ とし、 それぞれの木になっている実の個数を数列 $ A\ =\ (A_1,\ A_2,\ A_3,\ A_4,\ A_5) $ を用いて表すことにします。 - $ 0 $ 日目、$ A\ =\ (0,\ 0,\ 0,\ 0,\ 0) $ です。 - $ 1 $ 日目の朝、それぞれの木に新たに実がなり、$ A\ =\ (1,\ 2,\ 3,\ 4,\ 5) $ となります。 - $ 2 $ 日目の朝、それぞれの木に新たに実がなり、$ A\ =\ (2,\ 4,\ 6,\ 8,\ 10) $ となります。 - $ 2 $ 日目の夜、高橋君は $ 1 $ 回目の収穫を行います。$ 4\ +\ 6\ =\ 10 $ 個の木の実を収穫し、$ A\ =\ (2,\ 0,\ 0,\ 8,\ 10) $ となります。 - $ 3 $ 日目の朝、それぞれの木に新たに実がなり、$ A\ =\ (3,\ 2,\ 3,\ 12,\ 15) $ となります。 - $ 3 $ 日目の夜、高橋君は $ 2 $ 回目の収穫を行います。$ 3\ +\ 12\ =\ 15 $ 個の木の実を収穫し、$ A\ =\ (3,\ 2,\ 0,\ 0,\ 15) $ となります。 - $ 4 $ 日目の朝、それぞれの木に新たに実がなり、$ A\ =\ (4,\ 4,\ 3,\ 4,\ 20) $となります。 - $ 5 $ 日目の朝、それぞれの木に新たに実がなり、$ A\ =\ (5,\ 6,\ 6,\ 8,\ 25) $となります。 - $ 5 $ 日目の夜、高橋君は $ 3 $ 回目の収穫を行います。$ 5\ +\ 6\ +\ 6\ +\ 8\ +\ 25\ =\ 50 $ 個の木の実を収穫し、$ A\ =\ (0,\ 0,\ 0,\ 0,\ 0) $ となります。 ### Sample Explanation 2 $ 998244353 $ で割ったあまりを出力することに注意してください。