secvente

Notăm cu $[x; y]$, o secvență de numere naturale nenule $x, x + 1, x + 2, \ldots, y$, cu $x \leq y$.

Considerăm că secvența $[p; q]$ include secvența $[a; b]$ dacă are loc relația $p \leq a \leq b \leq q$.

Se dau $N$ secvențe speciale de forma $[a; b]$ și apoi $T$ secvențe de interogare $[L;R]$. Orice secvență care include cel puțin o secvență specială va fi numită secvență super-specială. Numărul de secvențe super-speciale pe care o secvență $[L; R]$ le include va fi denumit capacitatea secvenței $[L; R]$.

Cerință

Pentru fiecare secvență de interogare, să se determine capacitatea sa.

Date de intrare

Fișierul de intrare secvente.in conține pe prima linie numărul natural $N$, reprezentând numărul de secvențe speciale. Pe următoarele $N$ linii se află câte două numere naturale nenule $a$ și $b$, separate printr-un spațiu, reprezentând secvențele speciale.

Pe linia $N+2$ se află numărul natural $T$, reprezentând numărul de secvențe de interogare, iar pe următoarele $T$ linii se află câte două numere naturale nenule $L$ și $R$, separate printr-un spațiu, reprezentând secvențele de interogare.

Date de ieșire

Fișierul de ieșire secvente.out va conține $T$ linii. Pe cea de a $i$-a linie din fișier se va scrie un singur număr natural, reprezentând capacitatea celei de a $i$-a secvențe de interogare, în ordinea din fișierul de intrare.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $1 \leq a \leq b \leq 1 \ 000 \ 000 \ 000$
• $1 \leq T \leq 100 \ 000$
• $1 \leq L\leq R \leq 1 \ 000 \ 000 \ 000$
• Pentru teste în valoare de $79$ de puncte, $b \leq 1 \ 000 \ 000$
• Pentru teste în valoare de $32$ de puncte, $N, T \leq 10 \ 000$

Exemplul 1

secvente.in

2
2 4
3 3
3
2 4
1 5
2 5

secvente.out

4
9
6

Explicație

Secvența de interogare $[2;4]$ conține secvențele super-speciale $[2;3]$, $[2;4]$, $[3;3]$ și $[3;4]$. Se observă că $[2; 2]$ nu este o secvență super-specială deoarece nu include pe niciuna dintre cele două secvențe speciale ($[2, 4]$ și $[3, 3]$).

Secvența de interogare $[1;5]$ conține secvențele super-speciale $[1;3]$, $[1;4]$, $[1;5]$, $[2;3]$, $[2;4]$, $[2;5]$, $[3;3]$, $[3;4]$ și $[3;5]$.

Secvența de interogare $[2;5]$ conține secvențele super-speciale $[2;3]$, $[2;4]$, $[2;5]$, $[3;3]$, $[3;4]$ și $[3;5]$.