Fișierul intrare/ieșire	soparla.in, soparla.out	Sursă	ad-hoc
Autor	autor necunoscut	Adăugată de	Alexandru Petrescu • alexpetrescu
Timp de execuție pe test	0.17 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Șopârla (clasa a 9-a)

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.

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

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.

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

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

Precizare

• Inițial borcanele sunt goale.

Exemplu

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.