题目描述

在库存管理系统中，跟踪和调节商品库存量是关键任务之一。小蓝经营的仓库中存有多种商品，这些商品根据类别和规格被有序地分类并编号，编号范围从 $1$ 至 $n$。初始时，每种商品的库存量均为 $0$。

为了高效地监控和调整库存量，小蓝的管理团队设计了 $m$ 个操作，每个操作涉及到一个特定的商品区间，即一段连续的商品编号范围（例如区间 $[L, R]$）。执行这些操作时，区间内每种商品的库存量都将增加 $1$。然而，在某些情况下，管理团队可能会决定不执行某些操作，使得这些操作涉及的商品区间内的库存量不会发生改变，维持原有的状态。

现在，管理团队需要一个评估机制，来确定如果某个操作未被执行，那么最终会有多少种商品的库存量为 $0$。对此，请你为管理团队计算出，对于每个操作，如果不执行该操作而执行其它操作，库存量为 $0$ 的商品的种类数。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，分别表示商品的种类数和操作的个数。

接下来的 $m$ 行，每行包含两个整数 $L$ 和 $R$，表示一个操作涉及的商品区间。

输出格式

输出 $m$ 行，每行一个整数，第 $i$ 行的整数表示如果不执行第 $i$ 个操作，则最终库存量为 $0$ 的商品种类数。

5 3
1 2
2 4
3 5

1
0
1

提示

【样例说明】

考虑不执行每个操作时，其余操作对商品库存的综合影响：

• 不执行操作 $1$：剩余的操作是操作 $2$（影响区间 $[2, 4]$）和操作 $3$（影响区间 $[3, 5]$）。执行这两个操作后，商品库存序列变为 $[0, 1, 2, 2, 1]$。在这种情况下，只有编号为 $1$ 的商品的库存量为 $0$。因此，库存量为 $0$ 的商品种类数为 $1$。

• 不执行操作 $2$：剩余的操作是操作 $1$（影响区间 $[1, 2]$）和操作 $3$（影响区间 $[3, 5]$）。执行这两个操作后，商品库存序列变为 $[1, 1, 1, 1, 1]$。在这种情况下，所有商品的库存量都不为 $0$。因此，库存量为 $0$ 的商品种类数为 $0$。

• 不执行操作 $3$：剩余的操作是操作 $1$（影响区间 $[1, 2]$）和操作 $2$（影响区间 $[2, 4]$）。执行这两个操作后，商品库存序列变为 $[1, 2, 1, 1, 0]$。在这种情况下，只有编号为 $5$ 的商品的库存量为 $0$。因此，库存量为 $0$ 的商品种类数为 $1$。

【评测用例规模与约定】

对于 $20\%$ 的评测用例，$1 \le n,m \le 5 \times 10^3$，$1\le L \le R \le n$。
对于所有评测用例，$1 \le n,m \le 3 \times 10^5$，$1 \le L \le R \le n$。