{"raw_statement":[{"iden":"statement","content":"有 $n$ 个座位，从左到右编号为 $1 \\sim n$。现在有 $m$ 个小朋友，第 $i$ 个小朋友可以坐在 $l[i] \\sim r[i]$ 这些座位上，每个座位至多坐一个人。\n\n现在请问，如果只保留 $1 \\sim k$ 这些座位，最多可以给多少小朋友安排座位。请你输出 $k = 1 \\sim n$ 的所有答案。\n\n例如 $n = 3, m = 3$，$3$ 个小朋友 $A, B, C$ 的区间为 $[2, 2], [2, 3], [1, 3]$：\n\n- $k = 1$ 时：一个可行方案为 $[C]$，答案为 $1$；\n- $k = 2$ 时：一个可行方案为 $[C, B]$，答案为 $2$；\n- $k = 3$ 时：一个可行方案为 $[C, A, B]$，答案为 $3$；"},{"iden":"input","content":"第一行 $2$ 个整数 $n, m$ 代表座位和小朋友的数量。\n\n接下来 $m$ 行，每行 $2$ 个整数 $l[i], r[i]$ 代表第 $i$ 个小朋友的意愿区间。"},{"iden":"output","content":"输出 $n$ 行，第 $k$ 行代表只保留前 $1 \\sim k$ 个座位之后最多可以给几个小朋友安排座位。"},{"iden":"note","content":"### 样例 3-7\n\n见附件。\n\n### 数据范围\n\n对于所有数据，$1 \\leq n, m \\leq 2 \\times 10^5, 1 \\leq l[i] \\leq r[i] \\leq n$。\n\n本题采用捆绑测试，你必须通过子任务中的所有数据点以及其依赖的子任务，才能获得子任务对应的分数。\n\n| 子任务编号 | 分值 | 数据范围 | 特殊性质 | 子任务依赖 |\n|:------------:|:------:|:----------:|:----------:|:------------:|\n| 1          | 26   | $n, m \\leq 10$ |          |            |\n| 2          | 28   | $n, m \\leq 100$ |          | 1          |\n| 3          | 11   | $n, m \\leq 5000$ | $l[i] = r[i]$ |            |\n| 4          | 26   | $n, m \\leq 5000$ |          | 1,2,3      |\n| 5          | 9    | $n, m \\leq 2 \\times 10^5$ |          | 1,2,3,4    |"}],"translated_statement":null,"sample_group":[["3 3\n2 2\n2 3\n1 3","1\n2\n3"],["8 9\n5 7\n6 7\n5 6\n6 7\n7 7\n5 7\n4 6\n1 1\n7 7","1\n1\n1\n2\n3\n4\n5\n5"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}