3377. Distribution Center

输入格式

The input consists of a single test case, formatted as follows:

• 1st line: $n,m$
• The following $m$ lines: $x_i,y_i$.

An integer $n$ $(2\le n\le 200000)$ in the first line is the number of conveyor lanes. The lanes are numbered from $1$ to $n$, and two lanes with their numbers differing with 1 are adjacent. All of them start from the position $x=0$ and end at $x=100000$. The other integer $m$ $(1\le m<100000)$ is the number of robot arms.

The following $m$ lines indicate the positions of the robot arms by two integers $x_i$ $(0<x_i<100000)$ and $y_i$ $(1<y_i<n)$. Here, $x_i$ is the x-coordinate of the $i$-th robot arm, which can pick goods on either the lane $y_i$ or the lane $y_i+1$ at position $x=x_i$, and then release them on the other at the same x-coordinate.

You can assume that positions of no two robot arms have the same x-coordinate, that is, $x_i\ne x_j$ for any $i\ne j$.

输出格式

Output $n$ integers separated by a space in one line. The $i$-th integer is the number of the manufacturing lines from which the storage room connected to the conveyor lane $i$ can accept goods.

4 3
1000 1
2000 2
3000 3

2 3 4 4

4 3
1 1
3 2
2 3

2 4 4 2