Elevi Pentru Elevi Arges - IX | Dip4

(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 $N$ 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 $N$ mașini circulă pe rută, va trebui să răspundeți la $Q$ întrebări ale lui Doru, de tipul:
"Câte mașini se află în secunda $T_j$ (cu $1 \le j \le Q$) pe ruta DIP4?"

Date de intrare

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

• $N$ - numărul de mașini;
• $Q$ - numărul de întrebări;
• $S$ - numărul de secunde dintr-o zi pe Marte.

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

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

Date de ieșire

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

Restricții și precizări

• $1 \le N \le 6 \cdot 10^4$
• $1 \le Q \le 10^5$
• $1 \le S \le 10^6$
• $1 \le X_i \le Y_i < S$, cu $1 \le i \le N$
• $1 \le T_j < S$, cu $1 \le j \le Q$
• $[X_i, Y_i]$ reprezintă un interval închis la ambele capete, deci sunt incluse valorile $X_i$ și $Y_i$.
• Se acordă 10 puncte din oficiu.

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 $6$ mașini, ce se deplasează conform următorului grafic, cu semnificațiile:

• Pe axa Ox sunt reprezentate secundele, de la $0$ la $35$;
• Pe axa Oy sunt reprezentate mașinile de la $1$ la $6$;
• Segmentul colorat $i$ paralel cu axa Ox reprezintă a $i$-a mașină;
• Liniile paralele cu axa Oy reprezintă întrebările date.

Sunt $30$ de secunde într-o zi. Doru întreabă de $5$ ori câte mașini se află la un moment dat pe ruta DIP4, astfel:
Prima întrebare este referitoare la secunda $10$. Se poate observa că în acel moment se află pe rută prima, a treia și a patra mașină, deci răspunsul este $3$.
A doua întrebare este referitoare la secunda $23$. Se poate observa că în acel moment se află pe rută doar a șasea mașină, deci $1$.
A treia întrebare este referitoare la secunda $18$. Se poate observa că în acel moment se află pe rută doar a patra mașină, deci $1$.
A patra întrebare este referitoare la secunda $3$. Se poate observa că în acel moment se află pe rută a doua și a patra mașină, deci răspunsul este $2$.
A cincea întrebare este referitoare la secunda $28$. Se poate observa că în acel moment nu se află nici măcar o mașină pe rută, deci $0$.