Cho \(2\) mảng \(a\) và \(b\) gồm \(n\) phần tử gồm các số nguyên không âm và số nguyên dương \(k\).

Ở mỗi thao tác bạn có quyền chọn \(1\) số có giá trị \(i\) \((1 \leq i \leq n)\) sau đó hoán đổi giá trị \(a_{i}\) và \(b_{i}\).

Nhiệm vụ của bạn là tìm số thao tác nhỏ nhất để \(\sum_{i=1}^{n} a_{i}\) có giá trị bằng \(j\) (với \(j\) là các số tự nhiên từ \(1\) đến \(k\)).

Input

• Dòng đầu tiên gồm số \(n\) và \(k\) \((1 \leq n, k \leq 10^{5})\).
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa \(2\) số \(a_{i}\) và \(b_{i}\) \((1 \leq \sum_{i = 1}^{n} (a_{i} + b_{i}) \leq 2 \times 10^{5})\).

Output

• Gồm \(k\) dòng, dòng thứ \(j\) in ra số lượng thao tác ít nhất để \(\sum_{i=1}^{n} a_{i}\) có giá trị bằng \(j\), nếu không tồn tại cách nào thì in ra \(-1\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(1 \le n, k \le 2000, 1 \le \sum_{i =1}^{n} (a_{i} + b_{i}) \le 2000\).
• Subtask \(2\) (\(50\%\) số điểm): Không có rằng buộc gì thêm.

Example

3 5
1 3
2 5
0 7

-1
-1
0
-1
1