分数: 2000 点
问题陈述
有 M 竞争程序员(kyopro-ers)的数量 1 to M,他们将在接下来的 N 天里访问东京。 Kyopro-er i 将从 L_i日待到 R_i- 第天 (1 \leq L_i \leq R_i \leq N).
日。Maroon 正计划与他们举行晚宴。 如果晚宴在 x- 第天 (1 \leq x \leq N日举行,他可以与所有 kyopro-ers 交朋友 i 与 L_i \leq x \leq R_i.
对于每个 k=1,2,\cdots,N,解决以下问题。
- 如果 Maroon 举办恰好 k 次晚宴,他最多可以结交多少 kyopro-ers。
约束
- 1 \leq N \leq 10^6
- 1 \leq M \leq 10^6
- 1 \leq L_i \leq R_i \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M L_1 R_1 L_2 R_2 \vdots L_M R_M
输出
打印 N 行。 的 i- 第行应包含以下问题的答案 k=i.
示例输入 1
3 3 1 1 1 2 3 3
示例输出 1
2 3 3
- k=1:如果他在第 1天举办晚宴,他可以与 kyopro-ers 第 1 和 2.
- k=2:如果他在第 1-st 和 3天结为朋友。 1, 2,和 3.
- k=3:如果他在第 1-st, 2-nd,和 3天结为朋友。 1, 2,和 3.
示例输入 2
4 4 1 1 2 2 3 3 4 4
示例输出 2
1 2 3 4
示例输入 3
3 6 1 1 1 2 1 2 2 3 2 3 3 3
示例输出 3
4 6 6
示例输入 4
20 15 15 19 1 8 6 11 3 11 11 17 6 6 16 20 7 11 11 14 2 19 1 3 7 7 6 19 14 15 15 15
示例输出 4
7 11 12 13 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15