optimize-1

Find the minimum (m) and maximum (M) integer values taken by the function $f(x)=a_1(x+b_1)^2 + ... + a_N(x+b_N)^2$ on different [L, R] intervals, considering only integer $f(x)$ values $x\in [L,R]$.

Input specification

The first line contains $T$, the number of test cases. Description of each test case: First line: $N$ Then $N$ lines, each containing $a_k~~b_k~~(k=1,\ldots,N)$. Next line: $Q$ the number of queries. Then $Q$ lines follow, each containing $L_k~~R_k~~(k=1,\ldots,Q)$

Output specification

For each test case, output the corresponding $m$ and $M$ values for each query.

Constraints

$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$

Sample input 1

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

Sample output 1

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