题目描述

在库存管理系统中，跟踪和调节商品库存量是关键任务之一。

小蓝经营的仓库中存有多种商品，这些商品根据类别和规格被有序地分类并编号，编号范围从 $1$ 至 $n$。

初始时，每种商品的库存量均为 $0$。

为了高效地监控和调整库存量，小蓝的管理团队设计了 $m$ 个操作，每个操作涉及到一个特定的商品区间，即一段连续的商品编号范围（例如区间 [L, R]）。

执行这些操作时，区间内每种商品的库存量都将增加 $1$。

然而，在某些情况下，管理团队可能会决定不执行某些操作，使得这些操作涉及的商品区间内的库存量不会发生改变，维持原有的状态。

现在，管理团队需要一个评估机制，来确定如果某个操作未被执行，那么最终会有多少种商品的库存量为 $0$。

对此，请你为管理团队计算出，每个操作未执行时，库存量为 $0$ 的商品的种类数。

输入格式

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

输出格式

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

样例

样例输入 1

5 3
1 2
2 4
3 5

样例输出 1

1
0
1

提示

数据范围

• 对于 20% 的评测用例，$1 ≤ n$, $m ≤ 5$×$10$³，$1 ≤ L$ ≤ $R$ ≤ $n$。
• 对于所有评测用例，$1 ≤ n$, $m ≤ 3$×$10$⁵，$1 ≤ L$ ≤ $R$ ≤ $n$。