Fişierul intrare/ieşire:	ninja.in, ninja.out	Sursă	Algoritmiada 2014, Runda 2
Autor	Adrian Budau	Adăugată de	Adrian Budau •freak93
Timp execuţie pe test	0.75 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Ninja

Ninja A şi Ninja B vor să comită un furt respectabil. Respectabil în sensul că ceilalţi membri ai comunităţii ninja ar fi oarecum impresionaţi, deoarece până acum Ninja A şi Ninja B au comis infracţiuni cu cifra de afaceri în jurul a 3 portocale şi o amendă RATB. De această dată, cei doi vor să jefuiască rezervele de aur ale Băncii Naţionale. Acestea se află într-o cameră dreptunghiulară de dimensiune M x N. Fiecare rând al acestei camere conţine exact o grămadă de aur. Grămezile conţin lingouri de aur. Un lingou de aur de lungime L se întinde pe L coloane ale matricei. O grămadă de aur de dimensiune X, unde X este un număr impar, situată pe intervalul de coloane [LEFT, RIGHT] este constituită dintr-un lingou de aur de lungime X deasupra căruia se află o grămadă de dimensiune X - 2, situată pe intervalul de coloane [LEFT + 1, RIGHT - 1]. În cazul în care dimensiunea grămezii este egală cu 1 atunci aceasta nu are niciun alt lingou deasupra sa.

Fiecare coloană a camerei este dotată cu o cameră de vedere. Camera situată pe coloana C supraveghează toate lingourile care se suprapun cu coloana C.
Ninja A şi Ninja B se întreabă câte lingouri de aur ar rămâne nesupravegheate dacă ar stinge toate camerele de supraveghere din intervalul de coloane [R, C]. Ei vă cer răspunsul pentru mai multe întrebări de acest gen.

Date de intrare

Fişierul de intrare ninja.in va conţine trei numere naturale N, M, K reprezentând numărul de coloane, numărul de linii ale camerei respectiv numărul de întrebări la care trebuie să răspundeţi. Următoarele M linii vor conţine câte două numere X Y reprezentând faptul că pe linia respectivă se află o grămadă de aur situată pe intervalul de coloane [X, Y]. Următoarele K linii vor conţine de-asemenea două numere A B reprezentând o întrebare de tipul "Câte lingouri rămân nesupravegheate dacă se închid toate camerele din intervalul de coloane [A, B]?".

Date de ieşire

În fişierul de ieşire ninja.out se vor afla K linii fiecare conţinând un număr natural care reprezintă răspunsul la întrebarea corespunzătoare.

Restricţii

• 1 ≤ N, M, K ≤ 10⁵
• Atentie! M reprezintă numărul de linii al matricei.

Exemplu

Cum se trimit solutii?