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