== 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 ș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 câte ouă se vor afla în fiecare borcan la finalul celor *Q* zile.
h2. Date de intrare
Fișierul de intrare $soparla.in$ ...
Fișierul de intrare $soparla.in$ conține:
* 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$ ...
Î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[~j~]* ≤ *Y[~j~]* ≤ M
h2. Punctare
* 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") ==
