← 返回题目列表

AtCoder · abc255_h

Ex. 范围收获查询

中文机器翻译题面 查看原题

分数: 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.