Inventory Management: Zero Stock Evaluation

In the inventory management system, tracking and adjusting product stock levels is one key task. Blue's warehouse stores a variety of products, each of which is identified by a unique number from \(1\) to \(n\). Initially, the stock level of each product is \(0\).

To efficiently monitor and adjust the inventory, the management team has designed \(m\) operations. Each operation targets a continuous range of products, represented by an interval \([L, R]\). Executing an operation increases the stock level of every product within that range by \(1\). However, sometimes the team may decide not to execute a certain operation so that the stock levels of the products in that interval remain unchanged.

Your task is to evaluate, for each of the \(m\) operations if that specific operation is omitted while all others are executed, how many product types will have a final stock level of \(0\).

Note that if an operation is omitted, then for every product \(j\):

• If \(j \notin [L, R]\) then its stock remains as the sum of increments from all operations.
• If \(j \in [L, R]\) then its final stock becomes \(\text{total increments} - 1\).

A product will have a stock of \(0\) after omission if either:

• It is not in the omitted range and its total increments from all operations is \(0\), or
• It is in the omitted range and its total increments from all operations is \(1\) (since omitting the operation subtracts \(1\) to yield \(0\)).

For each operation \(i\) with range \([L_i, R_i]\), you should calculate:

\[ \text{answer}_i = \left(\#\{j \notin [L_i,R_i] : a_j = 0\}\right) + \left(\#\{j \in [L_i,R_i] : a_j = 1\}\right), \]

where \(a_j\) denotes the stock (i.e., number of increments) that product \(j\) gets when all operations are executed.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n, m \leq 10^5)\) representing the number of products and the number of operations.

Each of the next \(m\) lines contains two integers \(L\) and \(R\) \((1 \leq L \leq R \leq n)\) representing the range of product numbers for that operation.

outputFormat

Output \(m\) lines. The \(i\)-th line should contain a single integer indicating the number of product types whose final stock becomes \(0\) if the \(i\)-th operation is omitted (and all other operations are executed).

sample

5 3
1 3
2 4
3 5

1
0
1

</p>