题目描述

有 $N$ 个集合 $S_1,S_2,\ldots,S_N$。最初，$S_1,S_2,\ldots,S_N$ 都是空集合。

对这些集合进行 $Q$ 次如下操作。第 $i$ 次操作 $(1\le i\le Q)$ 给出整数三元组 $(L_i,R_i,X_i)$，并进行以下操作。

• 对 $S_{L_i},S_{L_i+1},\ldots,S_{R_i}$ 添加 $X_i$。

请对所有 $i=1,2,\ldots,N$，求出所有操作结束后的 $S_i$ 的元素个数。

输入格式

输入按以下格式从标准输入读入：

• $N$ $Q$
• $L_1$ $R_1$ $X_1$
• $L_2$ $R_2$ $X_2$
• $\vdots$
• $L_Q$ $R_Q$ $X_Q$

输出格式

请按顺序输出所有 $Q$ 次操作结束后的 $S_1$ 的元素个数、$S_2$ 的元素个数、$\ldots$、$S_N$ 的元素个数，用空格分隔。

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

进行 $5$ 次操作后，各个集合分别为 $\lbrace2\rbrace,\lbrace1,2\rbrace,\lbrace1,2,3\rbrace,\lbrace1,2,3\rbrace,\lbrace1,2,3\rbrace,\lbrace3\rbrace,\lbrace1\rbrace,\lbrace1\rbrace$。因此，请按顺序输出它们的元素个数 $1,2,3,3,3,1,1,1$，用空格分隔。

30 20
3 22 11
8 30 10
12 14 7
2 17 4
1 19 12
7 30 15
11 23 2
14 25 17
9 12 7
10 16 7
16 18 19
1 11 14
11 15 4
1 21 6
4 8 10
23 24 11
8 27 10
1 19 12
23 23 16
13 24 12

3 4 5 6 6 6 7 7 8 8 9 8 8 9 9 10 9 8 7 7 7 6 7 5 3 2 2 2 2 2

数据范围

• $1\le N\le2\times10^5$

• $1\le Q\le2\times10^5$

• $1\le L_i\le R_i\le N\ (1\le i\le Q)$

• $1\le X_i\le Q\ (1\le i\le Q)$

• 输入均为整数。

• 来源：AtCoder ABC 478 D

子任务设置

• 子任务 1（30 分）：$N, Q \le 2000$。
• 子任务 2（70 分）：无特殊限制。