配点 : $600$ 点

問題文

$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$ で割ったあまりを出力してください。

制約

• $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$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$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

$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)$ となります。

711741968710511029 1
82803157126515475 516874290286751784 588060532191410838

603657470

$998244353$ で割ったあまりを出力することに注意してください。