AT_wtf22_day1_d Welcome to Tokyo!

有 $M$ 位编号为 $1$ 到 $M$ 的竞赛程序员，在接下来的 $N$ 天内将访问东京。第 $i$ 位竞赛程序员会在第 $L_i$ 天到第 $R_i$ 天（$1 \leq L_i \leq R_i \leq N$）期间停留在东京。 maroon 君计划与他们举办聚餐。如果在第 $x$ 天（$1 \leq x \leq N$）举办聚餐，则可以与所有满足 $L_i \leq x \leq R_i$ 的竞赛程序员 $i$ 成为朋友。 对于每个 $k=1,2,\cdots,N$，请解决以下问题： - 如果恰好举办 $k$ 次聚餐，最多能与多少位竞赛程序员成为朋友？

输入以如下格式从标准输入给出。 > $N$ $M$ > $L_1$ $R_1$ > $L_2$ $R_2$ > $\vdots$ > $L_M$ $R_M$

输出 $N$ 行。第 $i$ 行输出 $k=i$ 时的答案。

### 限制条件 - $1 \leq N \leq 10^6$ - $1 \leq M \leq 10^6$ - $1 \leq L_i \leq R_i \leq N$ - 输入的所有值均为整数。 ### 样例说明 1 - $k=1$：如果在第 $1$ 天举办聚餐，可以与竞赛程序员 $1,2$ 成为朋友。 - $k=2$：如果在第 $1$ 天和第 $3$ 天举办聚餐，可以与竞赛程序员 $1,2,3$ 成为朋友。 - $k=3$：如果在第 $1,2,3$ 天都举办聚餐，可以与竞赛程序员 $1,2,3$ 成为朋友。 由 ChatGPT 4.1 翻译