Descriere

Se dau \(m\) puncte \(Q_j\) și \(n\) semiplane din \(\mathbb{R}^2\), oricare dintre ele orizontal (paralel cu axa \(Ox\)) sau vertical (paralel cu axa \(Oy\)), toate fiind definite prin inecuații de forma \(a_i x + b_i y + c_i \leq 0\).

Spunem că un dreptunghi este interesant dacă este determinat de unele dintre semiplanele date (nu neapărat toate semiplanele!). Mai precis, vârfurile sale sunt exact intersecții ale dreptelor suport ale unora dintre semiplane, laturile dreptunghiului sunt incluse în dreptele suport corespunzătoare, iar interiorul dreptunghiului este inclus în fiecare din semiplanele respective (altfel spus, dreptunghiul și interiorul său sunt exact intersecția semiplanelor respective).

În figura de mai jos sunt două dreptunghiuri interesante: \(A_1 A_2 A_4 A_3\), determinat de semiplanele \(a, b, c, d\) și \(A_1 A_2 A_6 A_5\), determinat de semiplanele \(a,b,c,e\). Dreptunghiul \(A_3 A_4 A_6 A_5\) nu este interesant. Chiar dacă vârfurile sale sunt date de intersecțiile semiplanelor \(a,b,d,e\) și laturile sale sunt incluse în dreptele suport ale acestora, interiorul său nu este inclus în intersecția semiplanelor respective.

Se cere să determinați pentru fiecare punct dacă se află în interiorul unui dreptunghi interesant (iar în cazul afirmativ, să spuneți care este aria minimă a unui dreptunghi interesant care îl conține).

Astfel, în figura de mai sus, sunt considerate punctele \(Q_1=(2, 0)\), \(Q_2=(1, 0)\), \(Q_3=(0, 0)\), \(Q_4=(0, -2.5)\):

• \(Q_1\) nu este situat în interiorul niciunui dreptunghi interesant.
• \(Q_2\) este pe laturile unor dreptunghi interesante, dar nu este în interiorul niciunuia dintre acestea.
• \(Q_3\) este situat în interiorul dreptunghiurilor interesante \(A_1 A_2 A_4 A_3\) și \(A_1 A_2 A_6 A_5\). Dintre acestea, \(A_1 A_2 A_4 A_3\) are aria minimă, egală cu \(8\).
• \(Q_4\) este situat în interiorul dreptunghiului interesant \(A_1 A_2 A_6 A_5\), de arie \(10\).

Recomandarea este să atacați această problemă după ce ați rezolvat-o cu succes pe cea precedentă.

Date de intrare

Se va citi de pe primul rând \(n\), numărul de semiplane care trebuie intersectate, și apoi \(n\) triplete de numere întregi \(a_i \ b_i \ c_i\), separate prin câte un spațiu, pe linii distincte, reprezentând coeficienții care definesc inecuația semiplanului \(i\): \(a_i x + b_i y + c_i \le 0\). Toate semiplanele citite vor fi fie orizontale, fie verticale (acest lucru nu mai trebuie verificat).

De pe următorul rând se va citi \(m\), numărul de puncte pentru care trebuie să determinați dacă se află în interiorul vreunui dreptunghi interesant sau nu. Pe următoarele \(m\) rânduri se vor afla perechi de numere reale \(x_{Q_j} \, y_{Q_j}\), separate printr-un spațiu, reprezentând coordonatele punctului \(Q_j (x_{Q_j}, y_{Q_j})\).

Date de ieșire

Pentru fiecare punct \(Q_j\) cu \(j = \overline{1, m}\), programul va afișa unul dintre următoarele șiruri de caractere:

• NO, dacă nu există niciun dreptunghi interesant sau dacă există dreptunghiuri interesante, dar punctul \(Q_j\) nu se află în interiorul niciunui astfel de dreptunghi.
• YES, dacă există cel puțin un dreptunghi interesant care să îl conțină pe \(Q_j\) în interior.

În cazul în care răspunsul de pe o linie este YES, pe următoarea linie trebuie afișat un număr real \(A_j\), reprezentând valoarea minimă a ariilor dreptunghiurilor interesante care îl conțin pe punctul \(Q_j\) în interior.

Aria dreptunghiurilor interesante poate fi un număr real. Aceasta se va afișa cu o precizie de 6 zecimale.

Restricții și precizări

• \(1 \leq n \leq 10\,000\)
• \(1 \leq m \leq 1000\)
• \(-10^6 \leq a_i, b_i, c_i \leq 10^6\)
• \(-10^6 \leq x_{Q_j}, y_{Q_j} \leq 10^6\)

Exemple

Exemplul 1

Input

3
-1 0 1
1 0 -2
0 1 3
1
1.5 -4

Output

NO

Explicație

Cele trei semiplane au inecuațiile \(-x + 1 \leq 0\), \(x - 2 \leq 0\), respectiv \(y + 3 \leq 0\). Inecuațiile pot fi rescrise \(x \geq 1\), \(x \leq 2\), \(y \leq -3\).

Punctele care întrunesc condiția \(1 \leq x \leq 2\) sunt cele din fâșia verticală dintre dreptele \(x = 1\) și \(x = 2\). Condiția \(y \leq -3\) ne obligă să le luăm pe cele care au ordonata mai mică sau egală cu \(-3\).

Intersecția oricăror semiplane din cele date este o mulțime nemărginită. Așadar, nu există niciun dreptunghi interesant, deci se va afișa NO.

Exemplul 2

Input

4
-1 0 1
1 0 -2
0 1 3
0 -2 -8
3
0 0
1 -3.5
1.25 -3.5

Output

NO
NO
YES
1

Explicație

Cele patru semiplane au inecuațiile \(-x + 1 \leq 0\), \(x - 2 \leq 0\), \(y + 3 \leq 0\), respectiv \(-2 y - 8 \leq 0\). Inecuațiile pot fi rescrise \(x \geq 1\), \(x \leq 2\), \(y \leq -3\), \(y \geq -4\).

Punctele care întrunesc condiția \(1 \leq x \leq 2\) sunt cele din fâșia verticală dintre dreptele \(x = 1\) și \(x = 2\). Punctele care întrunesc condiția \(-4 \leq y \leq -3\) sunt cele din fâșia orizontală dintre dreptele \(y = -4\) și \(y = -3\).

Intersecția lor este dreptunghiul determinat de punctele \(A=(1, -3), B=(1, -4), C=(2, -4), D=(2, -3)\), acesta este singurul dreptunghi interesant pentru datele de intrare considerate.

• Punctul \(Q_1\) nu este situat în interiorul acestui dreptunghi, iar pentru el se va afișa NO.
• Punctul \(Q_2\) este situat pe laturile acestui dreptunghi, nu în interiorul lui, deci se va afișa NO.
• Punctul \(Q_3\) este conținut în interiorul dreptunghiului, deci se va afișa YES, iar pe rândul următor se va afișa aria dreptunghiului, care este \(1\).

Exemplul 3

Input

11
-1 0 -1
0 -3 -6
0 2 -6
1 0 -3
0 1 -2
2 0 -10
0 -1 -3
-4 0 0
-1 0 1
0 -1 -1
1 0 -4
1
2 1

Output

YES
6

Explicație

Inecuațiile semiplanelor sunt: \(x \geq -1\), \(y \geq -2\), \(y \leq 3\), \(x \leq 3\), \(y \leq 2\), \(x \leq 5\), \(y \geq -3\), \(x \geq 0\), \(x \geq 1\), \(y \geq -1\), \(x \leq 4\).

Există mai multe dreptunghiuri interesante care îl conțin pe \(Q_1\), iar valoarea minimă a ariilor acestora este \(6\).