分数: 600 点
问题陈述
有 N 树。当天 0,每棵树都不结果实。
当天早上 1 及随后的日子里, i第棵树熊 i 每个都有新水果 i = 1, 2, \ldots, N.
高桥将表演 Q 收获。 对于每个 i = 1, 2, \ldots, Q, i第一次收获在白天晚上进行 D_i,收集剩余的所有水果 L_i-th 通过 此时的第 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-th 收获,取模 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-st 收获。 4 + 6 = 10 水果已收集,我们有 A = (2, 0, 0, 8, 10).
- 当天早上 3,每棵树都结出新的果实,我们有 A = (3, 2, 3, 12, 15).
- 在白天的晚上 3,高桥执行 2-nd收获。 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-rd收获。 5 + 6 + 6 + 8 + 25 = 50 水果已收集,我们有 A = (0, 0, 0, 0, 0).
示例输入 2
711741968710511029 1 82803157126515475 516874290286751784 588060532191410838
示例输出 2
603657470
请务必打印数字模数 998244353.