Rezolvare PBinfo #3003

Cerința

Pe un cerc sunt așezate echidistant N puncte, etichetate în sensul acelor de ceas cu 1, 2, 3, …, N.
Se dau M intervale de forma [a, b] și T interogări de forma P Q.

Pentru fiecare interogare [P, Q] să se verifice dacă este adevărat sau fals că intersecția tuturor intervalelor care au puncte comune cu [P, Q] include intervalul [P, Q].

Date de intrare

Fișierul de intrare intersectie.in conține pe primul rând numerele N, M și T. Pe următoarele M rânduri sunt scrise câte două numere naturale a b, separate prin spațiu, reprezentând capetele celor M intervale date. Pe următoarele T rânduri sunt scrise câte două numere naturale P Q, separate prin spațiu, reprezentând capetele celor T intervale de interogare date.

Date de ieșire

În fișierul de ieșire intersectie.out pe primele T rânduri este scris un număr natural: 1 dacă răspunsul la interogare este adevărat, respectiv 0 dacă răspunsul este fals.

Restricții și precizări

• 2 ≤ N ≤ 1.000.000.000
• 1 ≤ M ≤ 100.000
• 1 ≤ T ≤ 100.000
• 1 ≤ P ≤ N, 1 ≤ Q ≤ N, P și Q sunt etichete date în sensul acelor de ceas
• 1 ≤ a ≤ N, 1 ≤ b ≤ N, a și b sunt etichete date în sensul acelor de ceas
• Dacă x = y, atunci [x, y] este un interval care conține doar numărul x
• Pentru 30% din teste 1 ≤ M ≤ 1000 și 1 ≤ T ≤ 10.000
• Pentru 30% din teste 1 ≤ N ≤ 1.000.000

Exemplu:

intersectie.in

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

intersectie.out

0
0
1

Explicație

Intervalul [4,4] din interogarea 1 nu se intersectează cu nici unul din cele trei intervale date [2,3], [5,1], [5;5]. Răspuns 0.
Intervalul [3,5] din interogarea 2 se intersectează cu [2,3], [5,1], [5,5]. Intersecția acestora este vidă. Răspuns 0.
Intervalul [1,1] din interogarea 3 se intersectează doar cu [5,1]. Intersecția intervalelor care conțin pe [1,1] este [5,1]. Răspuns 1.