mere

În grădina lui Cosmin se află un măr cu număr nelimitat de mere. Cei $N$ prieteni ai lui Cosmin, numerotați de la $1$ la $N$, vor culege mere timp de $T$ zile, după următoarea regulă:
În dimineața zilei $T_i$, prietenii lui Cosmin vor forma o coadă la intrarea în grădina, începând cu prietenul $X_i$. Așadar, coada va arăta sub forma $X_i$, $X_{i+1}$, ..., $X_n$, $X_1$, ..., $X_{i-1}$. În acea zi se vor culege $Y_i$ mere. Fiecare prieten $X_i$ va intra în grădina, va culege un măr și se va întoarce în coadă.
În ziua $T + 1$, Cosmin alege aleatoriu $K$ prieteni ($Q_1..Q_k$) și dorește să afle câte mere a cules fiecare.

Cerinţă

Scrieţi un program care să găsească numărul de mere culese de fiecare dintre cei K prieteni selectați de Cosmin.

Date de intrare

Fişierul de intrare mere.in conţine:
Pe prima linie, $N \ T \ K$, trei numere întregi reprezentând numărul de prieteni, numărul de zile în care se vor culege mere și numărul de întrebări ale lui Cosmin.
Pe următoarele $T$ linii, câte două numere întregi, separate printr-un spațiu, $X_i \ Y_i$, reprezentând indicele prietenul ce va intra primul în grădina, respectiv numărul de mere ce vor fi culese în ziua $T_i$.
Pe ultima linie, $K$ numere întregi, $Q_i$, reprezentând indicii prietenilor lui Cosmin, pentru care se dorește aflarea numărului de mere culese.

Date de ieşire

Fişierul de ieşire mere.out va conţine $K$ numere întregi, pe o singură linie, separate printr-un spațiu, reprezentând răspunsurile la cele $K$ întrebări.

Restricţii şi precizări

• $1 \leq X_i \leq N \leq 10 \ 000 \ 000$;
• $1 \leq T \leq 200 \ 000$;
• $1 \leq K \leq 100 \ 000$;
• $1 \leq Y_i \leq 1 \ 000 \ 000$.
• Pentru teste în valoare de $30$ puncte: $1 \leq X_i \leq N \leq 100$, $1 \leq T \leq 100$, $1 \leq K \leq 100$, $1 \leq Y_i \leq 1 \ 000$;
• Pentru teste în valoare de $50$ puncte: $1 \leq X_i \leq N \leq 200.000$, $1 \leq T \leq 10 \ 000$, $1 \leq K \leq 10 \ 000$;
• Pentru teste în valoare de $70$ puncte: $1 \leq N \leq 1 \ 000 \ 000$, $1 <= T <= 100 \ 000$.

Exemplu

mere.in

5 3 4
1 2
3 5
2 7
2 4 1 2

mere.out

4 2 3 4

Explicație

$5$ persoane vor culege mere timp de $3$ zile, astfel:

• În prima zi, vor culege $2$ mere persoanele cu indicii $1$ și $2$;
• În a doua zi, vor culege $5$ mere persoanele cu indicii $3, 4, 5, 1$ și $2$;
• În a treia zi, vor culege $7$ mere persoanele cu indicii $2, 3, 4, 5, 1, 2, 3$.

Așadar, numărul de mere culese de fiecare persoană de la $1$ la $N$ este: $1 \rightarrow 3, 2 \rightarrow 4, 3 \rightarrow 3, 4 \rightarrow 2, 5 \rightarrow 2$.