Пиріг для пирога
У Бесі та Ельзи є по n пирогів. Кожен з цих 2n пирогів має свою оцінку смачності як на думку Бесі, так і на думку Ельзи (ці оцінки можуть відрізнятися).
Бесі хоче віддати один зі своїх пирогів Ельзі. Якщо Ельза отримує пиріг від Бесі, вона повинна віддати один зі своїх пирогів Бесі. Щоб не бути ні скупою, ні надто щедрою, Ельза намагатиметься вибрати пиріг, який буде не менш смачним (на її думку), ніж той, що вона отримала, але не більше ніж на d одиниць смачнішим. Якщо такого пирога немає, Ельза втече до Японії.
Якщо ж Ельза віддасть пиріг Бесі, то Бесі, у свою чергу, намагатиметься віддати Ельзі пиріг, який буде не менш смачним (на її думку), ніж той, що вона отримала, але не більше ніж на d одиниць смачнішим. Якщо Бесі не зможе цього зробити, вона теж втече. Інакше вона віддасть пиріг Ельзі. Цей обмін триває, поки це можливо, або поки одна з корів не отримає пиріг з оцінкою смачності 0. У такому випадку процес завершується, і обидві корови залишаються задоволеними.
Зазначимо, що один і той самий пиріг не може бути подарований двічі, і пиріг не може повернутися до тієї корови, яка його подарувала.
Для кожного з n пирогів Бесі можна вибрати його як початковий подарунок для Ельзи. Визначте мінімальну кількість обмінів, які можуть бути здійснені, щоб обидві корови залишилися задоволеними.
Вхідні дані
Перша строка містить два цілі числа n (1 ≤ n ≤ 10^5) і d (0 ≤ d ≤ 10^9). Наступні 2n строк містять по два цілі числа, розділені пробілом, що позначають смачність даного пирога на думку Бесі та на думку Ельзи відповідно.
Перші n строк стосуються пирогів Бесі, а решта n строк стосуються пирогів Ельзи.
Гарантовано, що всі оцінки смачності знаходяться в діапазоні [0, 10^9].
Вихідні дані
Вихід повинен містити n строк. Строка i повинна містити одне ціле число: мінімальну кількість обмінів, які можуть бути здійснені для щасливого завершення, якщо Бесі почне з пирога i. Якщо щасливе завершення при початку з пирога i неможливе, то строка i повинна містити -1.