optimize-1

Keressük meg az $f(x)=a_1(x+b_1)^2 + ... + a_N(x+b_N)^2$ függvény által különböző $[L,R]$ intervallumon felvett $f(x)$ egész számok közül a legkisebbet (m) és a legnagyobbat (M).

Bemenet specifikáció

Minden szereplő paraméter egész szám. Az első sorban van $T$ az esetek száma. Egy eset leírása: Az első sorban $N$, majd $N$ sor jön az $a_k~~b_k~~(k=1,\ldots,N)$ számokkal. A következő sorban van $Q$ a kérések száma, melyet $Q$ sor követ az $L_k~~R_k~~(k=1,\ldots,Q)$ számokkal.

Kimenet specifikáció

Minden esethez a kéréseknek megfelelő $m$ és $M$ értéket írjuk ki.

Korlátok

$1\le T \le 100$
$1\le N \le 100$
$-1\_000\le a_k \le 1\_000$
$-1\_000\le b_k \le 1\_000$
$1\le Q \le 10\_000$
$-100\_000\le R_k \le 100\_000$
$-100\_000\le L_k \le 100\_000$

1. példa bemenet

1. 1
2. 5
3. 8 7
4. 3 8
5. 10 5
6. 3 6
7. -7 3
8. 10
9. -4 2
10. -5 -5
11. -17 14
12. 3 13
13. -19 0
14. -19 5
15. 0 10
16. -15 -9
17. 1 2
18. -11 -8

1. példa kimenet

1. 135 1455
2. 34 34
3. -69 7767
4. 1794 7054
5. -69 2190
6. -69 2574
7. 879 5119
8. -30 894
9. 1150 1455
10. -65 142