← 返回题目列表

AtCoder · abc320_e

H. 素面流

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

分数: 475 点

问题陈述

有 N 人们聚集在一起参加名为“流动面条”的活动。人们排成一排,编号 1 to N 按从前到后的顺序。

活动期间,发生以下情况 M 次:

  • 时间 T_i,数量 W_i 面条飞下来。排在前面的人会得到所有的信息(如果这一排中没有人,则没有人会得到它)。然后,该人走出该行并在某个时间返回到其在该行中的原始位置 T_i+S_i.

某个时间返回该行的人 X 被认为在该时间行中 X.

毕竟 M 事件,报告每个人拥有的面条总量。

约束

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq M \leq 2\times 10^5
  • 0 <T_1 <\ldots < T_M \leq 10^9
  • 1 \leq S_i \leq 10^9
  • 1 \leq W_i \leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
T_1 W_1 S_1
\vdots
T_M W_M S_M

输出

打印 N 行。 的 i第行应包含面条人的数量 i 已经有了。


示例输入 1

3 5
1 1 3
2 10 100
4 100 10000
10 1000 1000000000
100 1000000000 1

示例输出 1

101
10
1000

活动进行如下:

  • 时间 1,数量 1 面条飞下来。人 1, 2,和 3 在这一排,前面的那个人,那个人 1,拿到面条并走出行列。
  • 时间 2,数量 10 面条飞下来。人 2 和 3 在这一排,前面的那个人,那个人 2,拿到面条并走出行列。
  • 时间 4, 人 1 返回到该行。
  • 时间 4,数量 100 面条飞下来。人 1 和 3 在这一排,前面的那个人,那个人 1,拿到面条并走出行列。
  • 时间 10,数量 1000 面条飞下来。唯一的人 3 在这一排,前面的人,人 3,拿到面条并走出行列。
  • 时间 100,数量 1000000000 面条飞下来。排里没有人,所以没人吃这些面条。
  • 时间 102, 人 2 返回到该行。
  • 时间 10004, 人 1 返回到该行。
  • 时间 1000000010, 人 3 返回到该行。

面条人总量 1, 2,和 3 有的是 101, 10,和 1000。


示例输入 2

3 1
1 1 1

示例输出 2

1
0
0

示例输入 3

1 8
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
8 8 8

示例输出 3

15