当前没有测试数据。

Ex - 范围收获查询

分数：$600$ 分

问题描述

有 $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 \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$，令 $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)$。

711741968710511029 1
82803157126515475 516874290286751784 588060532191410838

603657470

打印出的的每个数字都要对 $998244353$ 取模。