问题描述

有 $N$ 棵树。在第 $0$ 天，每棵树都没有结出果实。
从第 $1$ 天的早上开始，第 $i$ 棵树每天都会结出 $i$ 个新的果实，其中 $i = 1, 2, \ldots, N$。

高桥会进行 $Q$ 次收获。对于每次 $i = 1, 2, \ldots, Q$ 的收获，将在第 $D_i$ 天晚上进行，收集该时刻剩余在第 $L_i$ 到第 $R_i$ 棵树上的所有果实。

对于每一次收获，输出高桥将收集的果实数量，对 $998244353$ 取模。

约束条件

• $1 \leq N \leq 10^{18}$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq D_1 < D_2 < \cdots < 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$，令 $A_i$ 是第 $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$ 的计算。