Fişierul intrare/ieşire:	intersectie.in, intersectie.out	Sursă	ad-hoc
Autor		Adăugată de	Cosmin-Mihai Tutunaru •stocarul
Timp execuţie pe test	0.25 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Intersectie

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.

Cerinţă

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

• 2 ≤ N ≤ 10^9
• 1 ≤ M ≤ 10^5
• 1 ≤ T ≤ 10^5
• 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 ≤ 10000
• Pentru 30% din teste 1 ≤ N ≤ 10^6

Exemplu

Explicaţie

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

Cum se trimit solutii?