题目描述

苹果批发商阿宝的仓库前有一排 $N$ 个货摊，从左到右编号 $1$ 到 $N$。

今天阿宝要发 $Q$ 车苹果。第 $i$ 车车斗里装的都是同一品种的苹果，品种编号为 $X_i$；司机会把这一车苹果送到货摊 $L_i, L_{i+1}, \ldots, R_i$（含两端）的每一个货摊——哪怕某个货摊之前已经收到过这个品种，也照样再卸下一筐，直到所有的车都发完。

晚上清点时，阿宝想知道：每个货摊收到过多少种不同品种的苹果？同一个品种送来多少次都只算一种。

请对每个货摊 $i = 1, 2, \ldots, N$，求出它收到过的不同品种数。

输入格式

第一行两个整数 $N, Q$，分别表示货摊个数和发货车数。

接下来 $Q$ 行，第 $i$ 行三个整数 $L_i, R_i, X_i$，表示第 $i$ 车把品种 $X_i$ 的苹果送到货摊 $L_i$ 到 $R_i$。

输出格式

输出一行 $N$ 个整数，第 $i$ 个整数表示货摊 $i$ 收到过的不同品种数，用空格分隔。

样例 1

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

1 2 3 3 3 1 1 1

样例 2

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

1 3 2 1 2 2 2

样例解释

• 样例 1：发货结束后，各货摊收到过的品种集合依次为 $\{2\}, \{1,2\}, \{1,2,3\}, \{1,2,3\}, \{1,2,3\}, \{3\}, \{1\}, \{1\}$，大小分别为 $1,2,3,3,3,1,1,1$。
• 样例 2：货摊 $2$ 先后收到过品种 $1$（第 $1$ 车）、品种 $2$（第 $3$ 车）、品种 $3$（第 $5$ 车），共 $3$ 种；货摊 $4$ 收到的两车（第 $1$ 车和第 $2$ 车）都是品种 $1$，只算 $1$ 种。

数据范围与子任务

下发文件

对于全部测试点：

• $1 \le N, Q \le 2 \times 10^5$；
• $1 \le L_i \le R_i \le N$；
• $1 \le X_i \le Q$；
• 时间限制 $2$ 秒，空间限制 $256$ MiB。

子任务 3 的附加限制：对任意两次品种相同的发货 $i \ne j$，区间 $[L_i, R_i]$ 与 $[L_j, R_j]$ 没有公共货摊。

计分方式：子任务之间没有依赖关系。