该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

小朋友排成一排，老师给他们分苹果。

小朋友从左到右标号 1 至 N。有 M 个老师，每次第 i 个老师会给第 Li 个到第 Ri 个，一共 Ri - Li + 1 个小朋友每人发 Ci 个苹果。

最后老师想知道每个小朋友有多少苹果。

Format

Input

第一行两个整数 N、M，表示小朋友个数和老师个数。

接下来 M 行，每行三个整数 Li、Ri、Ci，意义如题目表述。 .

Output

一行 N 个数，第 i 个数表示第 i 个小朋友手上的水果。

Samples

5 3
1 2 1
2 3 2
2 5 3

1 6 5 3 3

Limitation

对于 100% 的数据，N、M ≤ 100000，1 ≤ Li ≤ Ri ≤ N，0 ≤ Ci ≤ 100。