Rezolvare PBinfo #2625

Stațiunea Xoni de pe insula Ixos are N magazine de înghețată, așezate unul lângă altul, pe aceeași parte a străzii pietonale. Acestea sunt numerotate cu valori naturale de la 1 la N , în ordinea așezării pe stradă.

Magazinele sunt deținute de K acționari (numerotați de la 1 la K ), fiecare dintre aceștia fiind proprietarul unor magazine numerotate consecutiv. Un magazin poate avea mai mulți acționari.

Odată cu venirea verii, începe și perioada concediilor, toți acționarii luându-și concediul împreună, timp de M zile. Înainte de a pleca în concediu, ei au discutat cu Transportel pentru a se ocupa de aprovizionarea cu înghețată a magazinelor lor. Acesta a decis, singur, să facă în fiecare dintre cele M zile aprovizionarea unor magazine, numerotate și acestea cu numere consecutive.

Cerința

Determinați, pentru fiecare acționar numărul de magazine deținute de către acesta care nu au fost aprovizionate cu înghețată în nicio zi din concediu.

Date de intrare

Prima linie a fișierului viitor.in conține trei numere naturale N , M și K separate prin câte un spațiu, cu semnificația de mai sus. Fiecare dintre următoarele M linii conține câte două numere naturale x și y, separate printr-un spațiu. Numerele x y aflate pe cea de a i-a linie dintre cele M semnifică faptul că în ziua i sunt aprovizionate cu înghețată toate magazinele cu numerele de ordine x , x+1 , …, y . Fiecare dintre următoarele K linii conține câte două numere naturale a și b , separate printr-un spațiu. Numerele a b situate pe a i-a linie dintre cele K semnifică faptul că proprietarul i este acționar la magazinele cu numerele a , a+1 , a+2 , …, b .

Date de ieșire

Fișierul viitor.out va conține K linii. Pe cea de a i-a linie se află numărul de magazine deținute de către acționarul i , care nu au fost aprovizionate cu înghețată în nicio zi din concediu.

Restricții și precizări

• 1 ≤ N ≤ 2 000 000 000
• 1 ≤ M ≤ 100 000
• 1 ≤ K ≤ 100 000
• Pentru teste valorând 30 de puncte, 1 ≤ N, M, K ≤ 1 000.
• 1 ≤ x ≤ y ≤ N, 1 ≤ a ≤ b ≤ N
• Se garantează că fiecare dintre cele N magazine are cel puțin un acționar.
• Fiind foarte departe în viitor, observăm că oamenii trăiesc mai mult, se deplasează mai repede, dar au și concedii mai lungi.

Exemplu:

viitor.in

10 3 2
1 4
9 10
3 6
1 7
4 10

viitor.out

1
2

Explicație

Magazinul 7 nu a fost aprovizionat în nicio zi, fiind singurul dintre cele deținute de primul acționar care nu primește înghețată în nicio zi. Dintre magazinele deținute de acționarul 2, cele cu numerele 7 și 8 nu primesc înghețată în nicio zi.