题目描述

我们有 $N$ 张卡片，编号从 $1$ 到 $N$。
第 $i$ 张卡片正面写着整数 $A_i$，背面写着整数 $B_i$。这里，$\sum_{i=1}^N (A_i + B_i) = M$。
对于每个 $k=0,1,2,...,M$，解决以下问题。

前 $N$ 张卡片按照正面可见的方式排列。你可以选择翻转 $0$ 到 $N$ 张卡片（包括 $0$ 张和 $N$ 张）。
为了使得可见数字的和等于 $k$，至少需要翻转多少张卡片？打印这些卡片的数量。
如果没有办法通过翻转卡片使得可见数字的和等于 $k$，则打印 $-1$。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• $0 \leq A_i, B_i \leq M$
• $\sum_{i=1}^N (A_i + B_i) = M$
• 输入中的所有值都是整数。

输入和输出

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

$N\ M$ $A_1\ B_1$ $A_2\ B_2$ $\vdots$ $A_N\ B_N$

输出应为 $M+1$ 行。第 $i$ 行应包含 $k=i-1$ 的问题的答案。

样例

样例输入 1

3 6
0 2
1 0
0 3

样例输出 1

1
0
2
1
1
3
2

例如，对于 $k=0$，只需翻转第 $2$ 张卡片，这样可见数字的和为 $0+0+0=0$。这个选择是最优的。
对于 $k=5$，翻转所有的卡片，可见数字的和为 $2+0+3=5$。这个选择也是最优的。

样例输入 2

2 3
1 1
0 1

样例输出 2

-1
0
1
-1

样例解释 2

没有办法通过翻转卡片使得可见数字的和等于 $k=0$ 或 $k=3$。

样例输入 3

5 12
0 1
0 3
1 0
0 5
0 2

样例输出 3

1
0
1
1
1
2
1
2
2
2
3
3
4