流水素面

题目描述

有 $N$ 个人参加一个名为「流水素面」的活动。人们排成一列，从前到后依次编号为 $1$ 到 $N$。

在活动中，以下事件会发生 $M$ 次：

在时刻 $T_i$，流下 $W_i$ 量的素面。队伍最前面的人获得全部素面（如果队伍为空，则无人获得）。然后那个人离开队伍，并在时刻 $T_i+S_i$ 回到队伍中原来的位置。

在时刻 $X$ 回到队伍的人，在时刻 $X$ 被视为在队伍中。

所有 $M$ 次事件结束后，报告每个人获得的素面总量。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$T_1$ $W_1$ $S_1$
$\vdots$
$T_M$ $W_M$ $S_M$

输出格式

输出 $N$ 行。

第 $i$ 行应输出第 $i$ 个人获得的素面总量。

样例

3 5
1 1 3
2 10 100
4 100 10000
10 1000 1000000000
100 1000000000 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$。

3 1
1 1 1

1
0
0

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

15

数据范围

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