Distribution Center

A factory has $n$ manufacturing lines and the same number of storage rooms. It also has the same number of conveyor lanes, laid out in parallel, that carry goods from each manufacturing line straight to the matching storage room. The plan is to install robot arms at several points between pairs of adjacent lanes. A robot arm picks goods up from one of the two lanes and puts them down on the other, and it works in the opposite direction too. Goods from different manufacturing lines then get mixed among the storage rooms.

The positions of the robot arms decide which storage rooms the goods of each manufacturing line can reach. Given the number of conveyor lanes and the positions of the robot arms, find, for each storage room, how many manufacturing lines can deliver goods to it.

The input is a single test case in the following format.

n m
x1 y1
...
xm ym

The integer $n$ ($2 \le n \le 200000$) on the first line is the number of conveyor lanes. The lanes are numbered from 1 to $n$, and two lanes whose numbers differ by 1 are adjacent. Every lane starts at $x = 0$ and ends at $x = 100000$. The other integer $m$ ($1 \le m < 100000$) is the number of robot arms.

Each of the following $m$ lines gives the position of a robot arm as two integers $x_i$ ($0 < x_i < 100000$) and $y_i$ ($1 \le y_i < n$). At $x = x_i$, the $i$-th robot arm picks goods up from lane $y_i$ or lane $y_i + 1$ and puts them down on the other lane at the same $x$ coordinate. Each item passing a robot arm independently either switches lanes there or stays on its lane.

No two robot arms share an $x$ coordinate, that is, $x_i \ne x_j$ whenever $i \ne j$.

The figure above shows the layout of the first example input.

Print $n$ integers on one line, separated by a space. The $i$-th integer is the number of manufacturing lines whose goods the storage room attached to conveyor lane $i$ can accept.