viitor

Time limit: 0.2s Memory limit: 10MB Input: viitor.in Output: viitor.out

Stațiunea Xoni de pe insula Ixos are NN 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 11 la NN, în ordinea așezării pe stradă.

Magazinele sunt deținute de KK acționari (numerotați de la 11 la KK), 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 MM 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 MM zile aprovizionarea unor magazine, numerotate și acestea cu numere consecutive.

Cerință

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 NN, MM și KK separate prin câte un spațiu, cu semnificația de mai sus. Fiecare dintre următoarele MM linii conține câte două numere naturale xx și yy, separate printr-un spațiu. Numerele xyx y aflate pe cea de a ii-a linie dintre cele MM semnifică faptul că în ziua i sunt aprovizionate cu înghețată toate magazinele cu numerele de ordine x,x+1,,yx, x+1, \dots, y. Fiecare dintre următoarele KK linii conține câte două numere naturale aa și bb, separate printr-un spațiu. Numerele aba b situate pe a ii-a linie dintre cele KK semnifică faptul că proprietarul ii este acționar la magazinele cu numerele a,a+1,a+2,,ba, a+1, a+2, \dots, b .

Date de ieșire

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

Restricții și precizări

  • 1N2 000 000 0001 \leq N \leq 2 \ 000 \ 000 \ 000
  • 1M100 0001 \leq M \leq 100 \ 000
  • 1K100 0001 \leq K \leq 100 \ 000
  • Pentru teste valorând 30 de puncte, 1N,M,K1 000.1 \leq N, M, K \leq 1 \ 000.
  • 1xyN,1abN1 \leq x \leq y \leq N, 1 \leq a \leq b \leq N
  • Se garantează că fiecare dintre cele NN 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.

Exemplul

viitor.in

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

viitor.out

1
2

Explicație

Magazinul 77 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 22, cele cu numerele 77 și 88 nu primesc înghețată în nicio zi.

Log in or sign up to be able to send submissions!