У Бориса та Іллі є по N поштових марок. Кожна із 2N марок має свою цінність на думку Бориса та цінність на думку Іллі.

Борис хоче віддати одну з марок Іллі. Якщо Ілля отримає марку від Бориса, то він має віддати одну із своїх марок Борису. Щоб не бути ні скупим, ні щедрим, Ілля постарається вибрати марку, як мінімум, таку ж цінну (на думку Іллі), як він отримав, але не більше, ніж на D одиниць ціннішу. Така марка може не існувати і тоді Ілля буде почувати себе нещасним.

Якщо Ілля віддасть марку взамін, то Борис аналогічно постарається віддати Іллі марку, як мінімум таку ж по цінності (на думку Бориса), але не більше, ніж на D одиниць ціннішу. Якщо такої марки не знайдеться, то Борис почуватиметься нещасним.

Такий цикл триватиме поки це можливо, або поки один із хлопців не отримає марку з цінністю 0. В цьому випадку хлопці будуть почуватися щасливими.

Одна і та ж марка не може бути подарована двічі і марка не може повернутися до того, хто її подарував.

Кожна із \(N\) марок може бути вибрана Борисом, як початковий подарунок для Іллі. Визначити мінімальну кількість марок, які можуть бути подаровані так, щоб обидва хлопці були щасливими.

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

Перший рядок містить цілі числа \(N\), \(D\) (\(1 \le N \le 10^5\), \(0 \le D \le 10^9\)). Наступні \(2N\) рядків містять по два цілих числа, розділених пропуском, які відповідно позначають цінність марки по критеріях Бориса та Іллі. Перші ідуть \(N\) марок Бориса, а наступні \(N\) - марки Іллі. Гарантується, що величини цінності марок знаходяться в інтервалі [\(0,10^9\)].

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

Вивід містить \(N\) рядків. Рядок \(i\) містить одне ціле число: мінімальну кількість марок, які можуть бути подаровані при щасливій кінцівці, якщо Борис почне з марки \(i\). Якщо ж щаслива кінцівка при початку з марки \(i\) неможлива, то слід вивести -1.

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

2 1
1 1
5 0
4 2
1 4

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

3
1