题目描述

有 $n$ 个座位，从左到右编号为 $1 \sim n$。现在有 $m$ 个小朋友，第 $i$ 个小朋友可以坐在 $l[i] \sim r[i]$ 这些座位上，每个座位至多坐一个人。

现在请问，如果只保留 $1 \sim k$ 这些座位，最多可以给多少小朋友安排座位。请你输出 $k = 1 \sim n$ 的所有答案。

例如 $n = 3, m = 3$，$3$ 个小朋友 $A, B, C$ 的区间为 $[2, 2], [2, 3], [1, 3]$：

• $k = 1$ 时：一个可行方案为 $[C]$，答案为 $1$；
• $k = 2$ 时：一个可行方案为 $[C, B]$，答案为 $2$；
• $k = 3$ 时：一个可行方案为 $[C, A, B]$，答案为 $3$；

输入格式

第一行 $2$ 个整数 $n, m$ 代表座位和小朋友的数量。

接下来 $m$ 行，每行 $2$ 个整数 $l[i], r[i]$ 代表第 $i$ 个小朋友的意愿区间。

输出格式

输出 $n$ 行，第 $k$ 行代表只保留前 $1 \sim k$ 个座位之后最多可以给几个小朋友安排座位。

3 3
2 2
2 3
1 3

1
2
3

8 9
5 7
6 7
5 6
6 7
7 7
5 7
4 6
1 1
7 7

1
1
1
2
3
4
5
5

提示

样例 3-7

见附件。

数据范围

对于所有数据，$1 \leq n, m \leq 2 \times 10^5, 1 \leq l[i] \leq r[i] \leq n$。

本题采用捆绑测试，你必须通过子任务中的所有数据点以及其依赖的子任务，才能获得子任务对应的分数。