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.