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 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 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 e curios cate oua se vor afla in fiecare borcan la finalul celor Q zile.

Date de intrare

Fișierul de intrare soparla.in contine:

• 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.

Date de ieșire

În fișierul de ieșire soparla.out se vor afla N numere, fiecare numar pe cate o linie, al i-lea numar reprezentand numarul de oua 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_i ≤ Y_i ≤ M

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

Precizare

• Initial, borcanele sunt goale.

Exemplu

Explicație

Dupa prima zi