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$.