== include(page="template/taskheader" task_id="soparla") ==
Marcel studiaza comportamentul soparlelor. El are N borcane in care pune oua de soparla. Acestea sunt de M tipuri. Tipul i de soparla depune intr-o zi cate un ou in borcanele de la A[~i~] la B[~i~]. Adica soparla de tipul i adauga cate un ou in borcanele A[~i~], A[~i~]+1, ..., B[~i~], unde A[~i~] si B[~i~] se cunosc.
Marcel studiază comportamentul șopârlelor. El are *N* borcane în care pune ouă de șopârlă. Șopârlele sunt de *M* tipuri. Tipul *i* de șopârlă depune într-o zi câte un ou în borcanele de la *A[~i~]* la *B[~i~]*. Mai exact, șopârla de tipul *i* adaugă câte un ou în borcanele *A[~i~]*, *A[~i~]+1*, ..., *B[~i~]*, unde *A[~i~]* și *B[~i~]* se cunosc.
Marcel stie ca in fiecare din cele Q zile unele soparle isi vor depune ouale, altele nu. Anume, in ziua i, soparlele cu indicii X[~i~], X[~i~]+1, ..., Y[~i~] isi vor depune ouale, dupa obiceiul fiecarei soparle. El cunoaste X[~i~] si Y[~i~]. Observam ca de-a lungul zilelor, unele soparle isi pot depune oua de mai multe ori, chiar si de 0 ori.
Marcel știe că în fiecare din cele *Q* zile unele șopârle își vor depune ouăle, altele nu. Anume, în ziua *j*, șopârlele cu indicii *X[~j~]*, *X[~j~]+1*, ..., *Y[~j~]* își vor depune ouăle, după obiceiul fiecărei șopârle. El cunoaște *X[~j~]* și *Y[~j~]*. Observăm că de-a lungul zilelor, unele șopârle pot depune ouă de mai multe ori sau niciodată.
Marcel e curios cate oua se vor afla in fiecare borcan la finalul celor Q zile.
Marcel e curios câte ouă se vor afla în fiecare borcan la finalul celor *Q* zile.
h2. Date de intrare
Fișierul de intrare $soparla.in$ contine:
Fișierul de intrare $soparla.in$ conține:
* pe prima linie, numerele N (numarul de borcane), M (numarul de soparle) si Q (numarul de zile)
* pe urmatoarele M linii, cate 2 numere A[~i~] si B[~i~], care delimiteaza intervalul borcanelor in care depune soparla i oua.
* pe urmatoarele Q linii, cate 2 numere X[~i~] si Y[~i~], care delimiteaza intervalul soparlelor care depun oua in ziua i.
* pe prima linie, numerele *N* (numărul de borcane), *M* (numărul de șopârle) și *Q* (numărul de zile)
* pe următoarele *M* linii, câte 2 numere *A[~i~]* și *B[~i~]*, care delimitează intervalul borcanelor în care depune șopârla *i* ouă
* pe următoarele *Q* linii, câte 2 numere *X[~j~]* și *Y[~j~]*, care delimitează intervalul șopârlelor care depun ouă în ziua *j*
h2. Date de ieșire
În fișierul de ieșire $soparla.out$ se vor afla N numere despartite prin cate un spatiu, al i-lea numar reprezentand numarul de oua din borcanul i la finalul celor Q zile.
În fișierul de ieșire $soparla.out$ se vor afla *N* numere, fiecare număr pe câte o linie, al [*i*]-lea număr reprezentând numărul de ouă din borcanul *i* la finalul celor *Q* zile.
h2. Restricții
* 1 ≤ N ≤ 100.000
* 1 ≤ M ≤ 100.000
* 1 ≤ Q ≤ 100.000
* 1 ≤ A[~i~] ≤ B[~i~] ≤ N
* 1 ≤ X[~i~] ≤ Y[~i~] ≤ M
* 1 ≤ *N* ≤ 100.000
* 1 ≤ *M* ≤ 100.000
* 1 ≤ *Q* ≤ 100.000
* 1 ≤ *A[~i~]* ≤ *B[~i~]* ≤ N
* 1 ≤ *X[~j~]* ≤ *Y[~j~]* ≤ M
h2. Punctare
* in 20% din teste, N ≤ 1000, M ≤ 1000, Q ≤ 1000
* in alte 20% din teste, N > 1000, M &le 1000, Q ≤ 1000
* in alte 20% din teste, N > 1000, M >1000, Q ≤ 1000
* in alte 20% din teste, N > 1000, M ≤ 1000, Q >1000
* in restul de 20% din teste, N > 1000, M > 1000, Q > 1000
* pentru 20% din teste, cunoaștem că *N* ≤ 1000, *M* ≤ 1000, *Q* ≤ 1000
* pentru alte 20% din teste, cunoaștem că *M* ≤ 1000 și *Q* ≤ 1000
* pentru alte 20% din teste, cunoaștem că *Q* ≤ 1000
* pentru alte 20% din teste, cunoaștem că *M* ≤ 1000
h2. Precizare
* Inițial borcanele sunt goale.
h2. Exemplu
table(example).
table(example).
|_. soparla.in |_. soparla.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|4 4 4
1 2
3 4
1 4
2 4
1 4
2 4
2 3
1 3
|6
8
10
10
|
h3. Explicație
...
Sunt 4 borcane și 4 șopârle care depun ouă vreme de 4 zile. În prima zi toate șopârlele vor depune ouă. Prima va depune în borcanele 1 și 2, a doua în borcanele 3 și 4, a treia în borcanele 1, 2, 3 și 4, iar a patra în borcanele 2, 3 și 4. Șirul numărului de ouă din fiecare borcan va arăta astfel: 2, 3, 3, 3.
În a doua zi, șopârlele 2, 3 și 4 vor depune ouă. A doua șopârlă va depune în borcanele 3 și 4, a treia în borcanele 1, 2, 3 și 4, iar a patra în borcanele 2, 3, și 4. Șirul numărului de ouă din fiecare borcan va arăta astfel: 3, 5, 6, 6.
În a treia zi, șopârlele 2 și 3 vor depune ouă. A doua șopârlă va depune în borcanele 3 și 4, iar a treia în borcanele 1, 2, 3 și 4. Șirul numărului de ouă din fiecare borcan va arata astfel: 4, 6, 8, 8.
În a patra zi, șopârlele 1, 2 și 3 vor depune ouă. Prima va depune În borcanele 1 și 2, a doua în borcanele 3 și 4 iar a treia în borcanele 1, 2, 3 și 4. Șirul numărului de ouă din fiecare borcan va arăta astfel: 6, 8, 10, 10. Acesta este șirul final, care trebuie afișat.
== include(page="template/taskfooter" task_id="soparla") ==
