Dip4

Time limit: 0.1s Memory limit: 3MB Input: dip4.in Output: dip4.outPoints by default: 10p

(Este anul 2077)

Oamenii au inventat mașini zburătoare cu viteză foarte mare, care pot călători între planete, pe anumite drumuri speciale. O astfel de rută, foarte populară, este cea dintre planeta Marte și planeta Venus, care poartă numele Drumul Interplanetar 4 (DIP4).

Doru, un om de pe Marte, care a reușit să ia permisul de curând, dorește să meargă pentru prima oară pe planeta Venus, folosind ruta DIP4. Pe acest drum se mai pot afla alte NN mașini zburătoare, care circulă într-un anumit interval de timp dat, exprimat prin prima și ultima secundă în care mașina se regăsește pe rută.

Doru nu este un șofer foarte experimentat, așa că vă roagă să-l ajutați să determine câte mașini se află în total pe drumul DIP4, în anumite secunde care-l interesează.

Cerință

Dându-se intervalele de timp în care fiecare din cele NN mașini circulă pe rută, va trebui să răspundeți la QQ întrebări ale lui Doru, de tipul:
"Câte mașini se află în secunda TjT_j (cu 1jQ1 \le j \le Q) pe ruta DIP4?"

Date de intrare

Pe prima linie a fișierului de intrare dip4.in se vor da:

  • NN - numărul de mașini;
  • QQ - numărul de întrebări;
  • SS - numărul de secunde dintr-o zi pe Marte.

Pe fiecare din următoarele NN linii se vor afla două numere XiX_i, YiY_i, reprezentând intervalul de secunde [Xi,Yi][X_i, Y_i] în care mașina cu indicele ii, cu 1iN1 \le i \le N, va circula pe ruta DIP4.

Pe fiecare din următoarele QQ linii se va afla câte un număr TjT_j, cu 1jQ1 \le j \le Q, care reprezintă al jj-lea moment de timp (secundă) pentru care trebuie determinat numărul de mașini de pe DIP4.

Date de ieșire

Pe primele QQ linii ale fișierului de ieșire dip4.out se va găsi câte un răspuns la fiecare întrebare QjQ_j, cu 1jQ1 \le j \le Q.

Restricții și precizări

  • 1N61041 \le N \le 6 \cdot 10^4
  • 1Q1051 \le Q \le 10^5
  • 1S1061 \le S \le 10^6
  • 1XiYi<S1 \le X_i \le Y_i < S, cu 1iN1 \le i \le N
  • 1Tj<S1 \le T_j < S, cu 1jQ1 \le j \le Q
  • [Xi,Yi][X_i, Y_i] reprezintă un interval închis la ambele capete, deci sunt incluse valorile XiX_i și YiY_i.
  • Se acordă 10 puncte din oficiu.
# Punctaj Restricții
1 40 1N1041 \le N \le 10^4, 1Q1041 \le Q \le 10^4, 1S1051 \le S \le 10^5
2 50 Fără restricții suplimentare

Exemplu

dip4.in

6 5 30
7 12
1 3
4 11
3 18
7 9
23 27
10
23
18
3
28

dip4.out

3
1
1
2
0

Explicație

Sunt 66 mașini, ce se deplasează conform următorului grafic, cu semnificațiile:

  • Pe axa Ox sunt reprezentate secundele, de la 00 la 3535;
  • Pe axa Oy sunt reprezentate mașinile de la 11 la 66;
  • Segmentul colorat ii paralel cu axa Ox reprezintă a ii-a mașină;
  • Liniile paralele cu axa Oy reprezintă întrebările date.

Sunt 3030 de secunde într-o zi. Doru întreabă de 55 ori câte mașini se află la un moment dat pe ruta DIP4, astfel:
Prima întrebare este referitoare la secunda 1010. Se poate observa că în acel moment se află pe rută prima, a treia și a patra mașină, deci răspunsul este 33.
A doua întrebare este referitoare la secunda 2323. Se poate observa că în acel moment se află pe rută doar a șasea mașină, deci 11.
A treia întrebare este referitoare la secunda 1818. Se poate observa că în acel moment se află pe rută doar a patra mașină, deci 11.
A patra întrebare este referitoare la secunda 33. Se poate observa că în acel moment se află pe rută a doua și a patra mașină, deci răspunsul este 22.
A cincea întrebare este referitoare la secunda 2828. Se poate observa că în acel moment nu se află nici măcar o mașină pe rută, deci 00.

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