Rezolvare PBinfo #4168

Notăm cu [x, y], o secvență de numere naturale nenule x, x + 1, x + 2, ..., y, cu x ≤ y.

Considerăm că secvența [p, q] include secvența [a, b] dacă are loc relația p ≤ a ≤ b ≤ 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ța

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 ≤ N ≤ 100.000
• 1 ≤ a ≤ b ≤ 1.000.000.000
• 1 ≤ T ≤ 100.000
• 1 ≤ L ≤ R ≤ 1.000.000.000

Exemplu:

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].