可翻转卡牌 2

题目描述

我们有 $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$。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$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

数据范围

• $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$
• 输入中的所有值均为整数。