Trapez

Se dau $N$ puncte în plan $(x_1, y_1), \ldots, (x_N, y_N)$ și $Q$ interogări $(\ell_1, r_1), \ldots, (\ell_Q, r_Q)$, cu $\ell_i < r_i$, la care va trebui să răspundeți. Toate numerele $x_i, y_i, \ell_i, r_i$ sunt întregi pozitivi.

Pentru o interogare $(\ell, r)$, răspunsul este după cum urmează. Fie $T(p, q)$ trapezul cu vârfurile $(\ell, p)$, $(r, q)$, $(r, 0)$, $(\ell, 0)$. Trapezul se numește valid dacă toate punctele $(x, y)$ cu $\ell \leq x \leq r$ dintre cele $N$ date se află în trapezul $T(p, q)$. Vrem să aflăm aria minimă a unui trapez valid $T(p, q)$, unde puteți alege $p$ și $q$ pentru a minimiza aria.
Deoarece aria trapezului este proporționala cu $r - \ell$, vrem să aflăm aria minimă împărțită la $r - \ell$.

Atenție! Valorile $p, q$ alese nu trebuie să fie neapărat întregi.

Date de intrare

Intrarea conține, pe primul rând, numerele $N$ și $Q$. Urmează $N$ linii, unde fiecare linie conține unul dintre punctele $(x_i, y_i)$ date. După, urmează $Q$ linii, unde fiecare linie conține una dintre interogările $(\ell_i, r_i)$.

Date de ieșire

Ieșirea trebuie să conțină $Q$ linii, fiecare conținând răspunsul pentru câte o interogare. Răspunsul se va scrie ca un număr zecimal, și se consideră corect dacă diferă de cel al comisie cu cel mult $10^{-1}$.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$.
• $1 \leq Q \leq 100 \ 000$.
• $1 \leq x_i, y_i \leq 10^9$.
• $1 \leq \ell_i < r_i \leq 10^9$.

Exemple

stdin

9 3
5 9
7 6
3 7
4 5
9 4
1 4
8 2
2 3
6 5
1 5
2 7
1 9

stdout

7
8.5
9

Explicații

Punctele sunt date conform următorului desen.

În prima interogare se consideră intervalul de coordonate $x$ între $1$ și $5$. Alegem $p = 4$ și $q = 10$, cu situația fiind conform desenului următor.

În a doua interogare se consideră intervalul de coordonate $x$ între $2$ și $7$. Alegem $p = 6$ și $q = 11$, cu situația fiind conform desenului următor.

În a treia interogare se consideră intervalul de coordonate $x$ între $1$ și $9$. Alegem $p = q = 9$, cu situația fiind conform desenului următor.