题目描述

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

题目大意

给定一片 $N$ 格的农田，从第 $0$ 天开始，第 $i$ 格农田每天会长出 $i$ 的作物。

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

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