Outside Little A's building is a large construction site with $N$ buildings to be built. Every day, buildings on this site are demolished and rebuilt. He often stares out the window, bored, counting how many buildings he can see.

To simplify the problem, we consider these events occurring on a 2D plane. Little A is located at $(0,0)$. The $i$-th building can be represented as a line segment connecting $(i,0)$ and $(i,H_i)$, where $H_i$ is the height of the $i$-th building. A building is considered visible if the line segment connecting $(0,0)$ to any point on the building with height greater than $0$ does not intersect any previous building segments.

The construction team works for $M$ days. Initially, no buildings have started construction, and all their heights are $0$. On the $i$-th day, the construction team changes the height of the building at $x$-coordinate $X_i$ to $Y_i$ (the height can be greater than the original—construction; smaller than the original—demolition; or even remain the same—the team did nothing that day). Please help Little A count how many buildings he can see after the construction team finishes their work each day.

Input

The first line contains two positive integers $N, M$.

The next $M$ lines each contain two positive integers $X_i, Y_i$.

Output

$M$ lines, where the $i$-th line contains an integer representing the number of buildings Little A can see after the $i$-th day.

Examples

Input 1

3 4
2 4
3 6
1 1000000000
1 1

Output 1

1
1
1
2

Constraints

For all data, $1 \leq X_i \leq N$, $1 \leq Y_i \leq 10^9$.

Other conditions:

• Test cases $1 \sim 4$: The construction team chooses a building uniformly at random each day and changes its height to a value chosen uniformly at random between $1$ and $10^9$.
• Test cases $5 \sim 10$: None.