Problem Description

In an inventory management system, tracking and adjusting product stock is one of the key tasks. Xiaolan runs a warehouse that stores many kinds of products. These products are classified and numbered in an orderly way by category and specification, with IDs ranging from $1$ to $n$. Initially, the stock of every product is $0$.

To efficiently monitor and adjust stock, Xiaolan's team designed $m$ operations. Each operation targets a specific product interval, i.e., a continuous range of product IDs (for example, the interval $[L, R]$). When an operation is executed, the stock of every product in the interval increases by $1$. However, in some cases, the team may decide not to execute certain operations, so the stock within the intervals of those operations will not change and will remain as it was.

Now the team needs an evaluation method to determine, if a certain operation is not executed, how many kinds of products will end up with stock $0$. Please compute, for each operation, the number of product types whose final stock is $0$ if this operation is not executed but all other operations are executed.

Input Format

The first line contains two integers $n$ and $m$, representing the number of product types and the number of operations.

The next $m$ lines each contain two integers $L$ and $R$, representing the product interval involved in an operation.

Output Format

Output $m$ lines, each containing one integer. The integer on line $i$ represents the number of product types whose final stock is $0$ if the $i$-th operation is not executed.

5 3
1 2
2 4
3 5

1
0
1

Hint

[Sample Explanation]

Consider the combined effect of the remaining operations when each operation is not executed:

• Do not execute operation $1$: the remaining operations are operation $2$ (affecting $[2, 4]$) and operation $3$ (affecting $[3, 5]$). After executing these two operations, the stock sequence becomes $[0, 1, 2, 2, 1]$. In this case, only product $1$ has stock $0$. Therefore, the number of product types with stock $0$ is $1$.

• Do not execute operation $2$: the remaining operations are operation $1$ (affecting $[1, 2]$) and operation $3$ (affecting $[3, 5]$). After executing these two operations, the stock sequence becomes $[1, 1, 1, 1, 1]$. In this case, no product has stock $0$. Therefore, the number of product types with stock $0$ is $0$.

• Do not execute operation $3$: the remaining operations are operation $1$ (affecting $[1, 2]$) and operation $2$ (affecting $[2, 4]$). After executing these two operations, the stock sequence becomes $[1, 2, 1, 1, 0]$. In this case, only product $5$ has stock $0$. Therefore, the number of product types with stock $0$ is $1$.

[Constraints and Notes for Test Cases]

For $20\%$ of the test cases, $1 \le n,m \le 5 \times 10^3$, $1 \le L \le R \le n$.
For all test cases, $1 \le n,m \le 3 \times 10^5$, $1 \le L \le R \le n$.

Translated by ChatGPT 5