Problem Statement

There are $N$ sets $S_1,S_2,\ldots,S_N$. Initially, $S_1,S_2,\ldots,S_N$ are all empty sets.

The following operation is performed $Q$ times on these sets. In the $i$-th operation $(1\le i\le Q)$, a triple of integers $(L_i,R_i,X_i)$ is given, and the operation below is performed.

• Add $X_i$ to $S_{L_i},S_{L_i+1},\ldots,S_{R_i}$.

For every $i=1,2,\ldots,N$, find the number of elements of $S_i$ after all operations are finished.

Constraints

• $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)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Output the number of elements of $S_1$, the number of elements of $S_2,\ldots,$ the number of elements of $S_N$ after all $Q$ operations are finished, in this order, separated by spaces.

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

After the five operations, the sets are $\lbrace2\rbrace,\lbrace1,2\rbrace,\lbrace1,2,3\rbrace,\lbrace1,2,3\rbrace,\lbrace1,2,3\rbrace,\lbrace3\rbrace,\lbrace1\rbrace,\lbrace1\rbrace$, respectively. Thus, output their numbers of elements, $1,2,3,3,3,1,1,1$, in this order, separated by spaces.

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

• Source: AtCoder ABC 478 D