102696: [AtCoder]ABC269 G - Reversible Cards 2

Problem Statement

We have $N$ cards numbered $1$ to $N$.
Card $i$ has an integer $A_i$ written on the front and an integer $B_i$ written on the back. Here, $\sum_{i=1}^N (A_i + B_i) = M$.
For each $k=0,1,2,...,M$, solve the following problem.

The $N$ cards are arranged so that their front sides are visible. You may choose between $0$ and $N$ cards (inclusive) and flip them.
To make the sum of the visible numbers equal to $k$, at least how many cards must be flipped? Print this number of cards.
If there is no way to flip cards to make the sum of the visible numbers equal to $k$, print $-1$ instead.

Constraints

• $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$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print $M+1$ lines. The $i$-th line should contain the answer for $k=i-1$.

Sample Input 1

3 6
0 2
1 0
0 3

Sample Output 1

1
0
2
1
1
3
2

For $k=0$, for instance, flipping just card $2$ makes the sum of the visible numbers $0+0+0=0$. This choice is optimal.
For $k=5$, flipping all cards makes the sum of the visible numbers $2+0+3=5$. This choice is optimal.

Sample Input 2

2 3
1 1
0 1

Sample Output 2

-1
0
1
-1

Sample Input 3

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

Sample Output 3

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

问题描述

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

样例输入 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