Laying Carpets

Problem Description

Dazhi's dad made money building subways, so he bought a lot of carpets and laid them over the living room again and again.

The living room is exactly a rectangle, and the width of the carpets matches the width of the room, so along the length the carpets overlap. The length of the room is $n$. Dazhi wants to know how many layers of carpet cover each $1$-metre segment.

Input Format

The first line contains $n, k$, where $n$ is the length of the room and $k$ is the number of carpets. $1 \le n, k \le 10^5$.

The following $k$ lines each contain a pair $[x, y]$, both integers, the start and end positions of the $i$-th carpet. $0 \le x < y \le n$.

Output Format

One line of integers, where the $i$-th number is the number of carpets covering the $i$-th metre.

Sample Input

4 3
1 3
0 2
1 4

Sample Output

1 3 2 1