当前没有测试数据。

G - 可逆卡片 2

分值 : $600$ 分

问题描述

给你 $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$ 张卡片（包括边界）并翻转它们。 为了使得正面的数的总和等于 $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$

...

$A_N$ $B_N$

输出

输出 $M+1$ 行。第 $i$ 行应该包含 $k=i-1$ 时的答案。

3 6
0 2
1 0
0 3

1
0
2
1
1
3
2

例如，对于 $k=0$，只需要翻转卡片 $2$，使得正面的数的总和为 $0+0+0=0$。这是最优选择。 对于 $k=5$，翻转全部的卡片，使得正面的数的总和为 $2+0+3=5$。这是最优选择。

2 3
1 1
0 1

-1
0
1
-1

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

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