[ABC255Ex] Range Harvest Query

给定一片 $N$ 格的农田，从第 $0$ 天开始，第 $i$ 格农田每天会长出 $i$ 的作物。 给出 $Q$ 个询问，每次询问以 $D,L,R$ 的格式给出，表示询问在第 $D$ 天，收割 $[L,R]$ 的农田，会获得多少作物？答案对 $998244353$ 取模。注意询问相互依赖，即在每一次收割后，$[L,R]$ 的作物应当清零。

[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 $ で割ったあまりを出力せよ。

5 3
2 2 3
3 3 4
5 1 5

10
15
50

711741968710511029 1
82803157126515475 516874290286751784 588060532191410838

603657470

### 制約 - $ 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 $ で割ったあまりを出力することに注意してください。