区间收获查询

题目描述

有 $N$ 棵树。第 0 天时，每棵树上都还没有果实。

从第 1 天开始，每天早晨，对每个 $i = 1, 2, \ldots, N$，第 $i$ 棵树上都会新长出 $i$ 个果实。

高桥君要进行 $Q$ 次收获作业。

对每个 $i = 1, 2, \ldots, Q$，第 $i$ 次收获作业在第 $D_i$ 天的晚上进行，收获此时第 $L_i$ 棵到第 $R_i$ 棵树上结的所有果实。

对每次收获作业，输出高桥君收获的果实数量对 $998244353$ 取模后的值。

输入格式

输入按以下格式从标准输入给出：

N Q
D_1 L_1 R_1
D_2 L_2 R_2
⋮
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$ 取模后的值。

数据范围

• $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$
• 输入中的所有值均为整数。