该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

水平排列着$W$个正方形格子，初始高度均为$0$。现在要依次堆叠$N$个高度为$1$的长方体砖块。砖块会粘附在高度为$h$的表面上，其顶部高度为$h+1$。

第$i$个砖块将覆盖从左数第$L_i$到第$R_i$的格子。砖块会粘附在其覆盖范围内最高的水平表面上。

对于每个砖块，输出其顶部的高度。

输入格式

输入从标准输入按以下格式给出：

$W$ $N$

$L_1$ $R_1$

$L_2$ $R_2$

$\vdots$

$L_N$ $R_N$

输出格式

第$i$行（$1 \leq i \leq N$）输出第$i$个砖块的顶部高度。

数据范围

• $2 \leq W \leq 5 \times 10^{5}$
• $1 \leq N \leq 2.5 \times 10^{5}$
• $1 \leq L_i \leq R_i \leq W$ $(1 \leq i \leq N)$
• 输入均为整数

有部分数据点满足：

1. $W \leq 9000$，$N \leq 9000$
2. $N \leq 9000$
3. 无额外约束

样例数据

100 4
27 100
8 39
83 97
24 75

1
2
2
3

说明

将第$i$个砖块称为砖块$i$。

砖块$1$粘附在格子表面上，顶部高度为$1$。

砖块$2$粘附在砖块$1$的顶部，顶部高度为$2$。

砖块$3$粘附在砖块$1$的顶部，顶部高度为$2$。

砖块$4$粘附在砖块$2$的顶部，顶部高度为$3$。

3 5
1 2
2 2
2 3
3 3
1 2

1
2
3
4
4

说明

砖块$1$粘附在格子表面上，顶部高度为$1$。

砖块$2$粘附在砖块$1$的顶部，顶部高度为$2$。

砖块$3$粘附在砖块$2$的顶部，顶部高度为$3$。

砖块$4$粘附在砖块$3$的顶部，顶部高度为$4$。

砖块$5$粘附在砖块$3$的顶部，顶部高度为$4$。

10 10
1 3
3 5
5 7
7 9
2 4
4 6
6 8
3 5
5 7
4 6

1
2
3
4
3
4
5
5
6
7

500000 7
1 500000
500000 500000
1 500000
1 1
1 500000
500000 500000
1 500000

1
2
3
4
5
6
7