题目描述

$1$ から $N$ までの番号がついた $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$ のときの答えを出力せよ。

题目大意

有 $n$ 张卡片，第 $i$ 张卡片正面有数字 $a_i$，背面有数字 $b_i$，同时 $\sum_{i=1}^n (a_i+b_i)=m$。所有卡片起初均被正面朝上地放置。

对于 $\forall k\in[0,m]$，输出使得所有卡片朝上的数字之和为 $k$ 时，需要翻面至少多少张卡片；如果不能通过翻面卡片使得所有卡片朝上的数字之和为 $k$ 则输出 $-1$。

$1\le n\le 2\times 10^5,0\le m\le 2\times 10^5,0\le a_i,b_i\le m$。

3 6
0 2
1 0
0 3

1
0
2
1
1
3
2

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$
• 入力される値はすべて整数

Sample Explanation 1

例えば $k=0$ のときは、カード $2$ のみを裏返せば見えている数の和を $0+0+0=0$ にすることができて、これが最適です。 また、$k=5$ のときは、すべてのカードを裏返せば見えている数の和を $2+0+3=5$ にすることができて、これが最適です。