У нас є \(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\)

Наступні  \(N\) рядків містять цілі числа \(A_i, B_i\)

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть \(M+1\) рядків. \(I\)-й рядок має містити відповідь для \(k=i-1\).

Примітка

До прикладу 1:

Для k=0, наприклад, маємо суму видимих ​​чисел 0+0+0=0. Цей вибір є оптимальним.

Для k=5 перегортання всіх карток дає суму видимих ​​чисел 2+0+3=5. Цей вибір є оптимальним.

Приклад вхідних даних

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