Fie A o mulțime de N puncte Ai în plan de coordonate întregi cunoscute (Ai.x, Ai.y). Pentru o întrebare definită printr-un punct Q=(Q.x, Q.y) se cere aria înfășurătorii convexe a punctelor: {Q} ∪ {Ai | Ai.x < Q.x și Ai ∈ A }.

Înfășurătoarea convexă a unei mulțimi de puncte este poligonul convex de arie minimă care conține toate punctele în interior sau pe laturile acestuia.

Cerinţă

Determinați răspunsurile pentru M întrebări de tipul enunţat mai sus, relativ la mulțimea inițială A.

Date de intrare

Pe prima linie a fişierului geometrie.in se află numerele naturale nenule N și M.
Următoarele N linii conțin câte două numere Ai.x Ai.y separate printr-un spațiu.
Următoarele M linii conțin câte două numere Q.x Q.y separate printr-un spațiu.
În fișierul de intrare atât punctele Ai cât și punctele Q sunt în ordinea crescătoare a valorilor x.

Date de ieşire

În fişierul geometrie.out vor fi M linii care conțin răspunsurile la întrebări, în ordinea în care au fost cerute, fiecare pe câte o linie. Afişaţi fiecare număr cu o zecimală precizie.

Restricţii şi precizări

• N, M ≤ 10^5
• Toate coordonatele Ai.x, Ai.y, Qx și Qy ≤ 10^9
• Punctele din mulțimea A au valori Xi distincte.
• Înfășurătoarea convexă a unei mulțimi cu cel mult două puncte are aria egală cu zero.
• Pentru teste în valoare de 20 puncte N ≤ 3
• Pentru teste în valoare de 40 puncte N×M ≤ 10^3
• Pentru teste în valoare de 60 puncte N×M ≤ 10^6

Exemplul 1

geometrie.in

3 3
1 3
4 5
5 1
3 3
6 8
8 4

geometrie.out

0.0
15.0
14.5

Exemplul 2

geometrie.in

9 2
1 3
3 5
4 1
6 4
8 6
9 1
10 3
11 5
13 2
4 3
10 4

geometrie.out

3.0
32.0

Explicație

Poligoanele formate din punctele care se obțin pentru cele doua întrebări de la exemplul 2 sunt: