题目描述

有 $N$ 个操作系统版本，按时间顺序编号为 $1,2,\dots,N$。共有 $N$ 台电脑，初始时第 $i$ 台电脑安装的系统版本为 $i$。

按顺序执行 $Q$ 次操作。第 $i$ 次操作具体为：

将所有当前系统版本为 $X_i$ 或更早的电脑升级到版本 $Y_i$（$Y_i>X_i$）。然后输出本次操作中被升级的电脑数量。

注意，对于 $i<Q$，第 $i$ 次操作的升级在进行第 $(i+1)$ 次操作前已经生效（操作是累积的）。

输入格式

输入共 $Q + 1$ 行；

• 第一行输入由空格隔开的两个正整数 $N, Q$；
• 接下来 $Q$ 行，第 $i$ $(1 \le i \le Q)$ 行输入由空格隔开的两个正整数 $X_i, Y_i$。

输出格式

输出 $Q$ 行，第 $i$ 行为第 $i$ 次操作中被升级的电脑数量。

样例输入

8 5
2 6
3 5
1 7
5 7
7 8

样例输出

2
1
0
3
7

说明

样例解释

该样例中共有 $5$ 次操作。

• 初始各台电脑的版本为 $1,2,3,4,5,6,7,8$。
• 第 $1$ 次操作：将版本 $\le2$ 的电脑升级到 $6$，升级了 $2$ 台，版本变为 $6,6,3,4,5,6,7,8$。
• 第 $2$ 次操作：将版本 $\le3$ 的电脑升级到 5，升级了 $1$ 台，版本变为 $6,6,5,4,5,6,7,8$。
• 第 $3$ 次操作：将版本 $\le1$ 的电脑升级到 $7$，升级了 $0$ 台，版本仍为 $6,6,5,4,5,6,7,8$。
• 第 $4$ 次操作：将版本 $\le5$ 的电脑升级到 $7$，升级了 $3$ 台，版本变为 $6,6,7,7,7,6,7,8$。
• 第 $5$ 次操作：将版本 $\le7$ 的电脑升级到 $8$，升级了 $7$ 台，最终所有版本都为 $8$。

数据范围

• 所有输入值均为整数
• $2\le N\le 10^6$；
• $1\le Q\le 2\times 10^5$；
• $1\le X_i<Y_i\le N$。