問題文

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

入力例 1

5 3
2 2 3
3 3 4
5 1 5

出力例 1

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

入力例 2

711741968710511029 1
82803157126515475 516874290286751784 588060532191410838

出力例 2

603657470

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