Подарунок#5278
14 серпня у світі відзначають два чудові свята: Міжнародна командна олімпіада з програмування серед паралелей A, A', і B та Всесвітній день дівчат у ЛКШ. Щоб відсвяткувати цю подію, старшокласники вирішили подарувати дівчатам у таборі необмежений Wi-Fi у кожному будиночку. Будиночки у ЛКШ — це прямокутники зі сторонами, паралельними осям координат; жоден з них не перетинає вісь (тобто пряму y = 0).
Після успішних перемовин з місцевим провайдером школярі отримали кілька роутерів і приймачів. Провайдер, однак, наполіг, щоб усі роутери встановлювалися поблизу найближчої дороги, що йде по прямій y = 0. Роутери потрібно з'єднати з сусідами вздовж цієї прямої кабелями, причому довжина будь-якого кабелю не повинна перевищувати .
Один роутер отримує інтернет від провайдера і передає його кабелем решті. Кожен роутер роздає бездротовий інтернет у радіусі . Для того щоб у будиночку був інтернет, у будь-якій точці всередині нього повинен бути встановлений приймач так, щоб ця точка була в радіусі дії хоча б одного роутера. Один роутер може обслуговувати будь-яку кількість приймачів.
Майже всі гроші було витрачено на колу та печиво, тому школярі хочуть мінімізувати кількість орендованих роутерів (приймачі надаються безкоштовно). Допоможіть визначити мінімально необхідну кількість роутерів.
У першому рядку записано три цілі числа: 1 \leq N \leq 100\,000 — кількість будиночків; 1 \leq dv, dh \leq 100\,000 — радіус дії роутеру та максимальна дозволена довжина кабелю. У кожному з наступних рядків міститься чотири цілі числа x_1, y_1, x_2, y_2, де x_1 < x_2 і y_1 < y_2, що описують прямокутник — будиночок з протилежними кутами у точках (x_1, y_1) і (x_2, y_2). Абсолютні значення всіх координат не перевищують . Усі числа у вхідних даних — цілі.
Виведіть мінімально необхідну кількість роутерів або -1, якщо розв'язку не існує.
Приклад 1