Diferențe pentru problema/soparla între reviziile #19 si #25

== include(page="template/taskheader" task_id="soparla") ==

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 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~] si Y[~j~]. Observăm că de-a lungul zilelor, unele șopârle pot depune ouă de mai multe ori sau niciodată.

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.

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$ 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

* 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, 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.

Î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

* 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 ≤ 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

h2. Exemplu

table(example).

table(example).

|_. soparla.in |_. soparla.out |
|4 4 4
1 2

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 oua din fiecare borcan va arăta astfel: 2, 3, 3, 3.

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 șitul final, care trebuie afișat.

Î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") ==