I kungariket JOI finns det $1$ tillräckligt lång väg som går i öst-västlig riktning. Det kungliga palatset i kungariket JOI ligger längs vägen, och en position längs vägen i kungariket JOI representeras av ett heltal $A$. När $A = 0$ representerar det det kungliga palatsets position. När $A > 0$ representerar det positionen $A$ meter öster om det kungliga palatset. När $A < 0$ representerar det positionen $-A$ meter väster om det kungliga palatset.

Längs vägen i kungariket JOI finns det $N$ hus, och husen är numrerade från $1$ till $N$ i ordning från väster till öster. Det finns $N$ medborgare i kungariket JOI, numrerade från $1$ till $N$. I hus $i$ bor medborgare $i$. Positionen för hus $i$ representeras av ett jämnt heltal $A_i$ skilt från $0$. Alla $A_1, \dots, A_N$ är olika.

I kungariket JOI har medborgarnas brist på motion på senare år blivit ett problem. Bekymrad över medborgarnas hälsa gav kungen av kungariket JOI order om att alla medborgare skulle gå på en promenad. När kungen ger ordern börjar alla medborgare samtidigt gå antingen österut eller västerut. Vilken riktning varje medborgare börjar gå i är bestämt i förväg för varje medborgare. Alla medborgare går med en hastighet av $1$ meter per $1$ sekund när de går.

Alla medborgare i kungariket JOI älskar att småprata. Om de möter en annan medborgare under promenaden stannar de på den platsen och börjar småprata. Detsamma gäller om de möter en medborgare som redan har stannat. En medborgare som en gång har stannat börjar aldrig gå igen.

Det finns $Q$ viktiga personer i kungariket JOI. Kungen av kungariket JOI vill ha reda på positionerna för de $Q$ viktiga personerna $T$ sekunder efter att ordern har getts. Skriv ett program som bestämmer positionerna för de $Q$ viktiga personerna $T$ sekunder efter att ordern har getts.

Indata

Indata består av $1 + N + Q$ rader.

På den $1$:a raden står $3$ heltal $N, T, Q$ ($1 \le N \le 100000 (= 10^5), 0 \le T \le 10^{18}, 1 \le Q \le 1000, 1 \le Q \le N$) separerade med mellanslag. Detta anger att det finns $N$ hus i kungariket JOI, och att kungen vill veta positionerna för de $Q$ viktiga personerna $T$ sekunder efter att ordern har getts.

På den $i$-te raden av de följande $N$ raderna står $2$ heltal $A_i, D_i$ ($-10^{18} \le A_i \le 10^{18}$, $A_i$ är ett jämnt tal skilt från $0$, $1 \le D_i \le 2$) separerade med mellanslag. $A_i$ är ett jämnt tal som representerar positionen för hus $i$. För alla $i$ ($1 \le i \le N - 1$) gäller $A_i < A_{i+1}$. $D_i$ representerar den riktning som medborgare $i$ börjar gå i efter att ordern har getts. När $D_i = 1$ börjar medborgare $i$ gå österut. När $D_i = 2$ börjar medborgare $i$ gå västerut.

På den $i$-te raden av de följande $Q$ raderna står ett heltal $X_i$ ($1 \le X_i \le N$). Detta anger att den $i$-te viktiga personen bor i hus $X_i$. För alla $i$ ($1 \le i \le Q - 1$) gäller $X_i < X_{i+1}$.

Bland de $5$ givna indatamängderna uppfyller Indata $1$ villkoren $N \le 100, T \le 10000$. Vidare uppfyller Indata $2$ villkoret $N \le 5000$. I Indata $3$ finns det ett heltal $M$ ($1 \le M \le N - 1$) sådant att $D_i = 1$ för alla $i$ ($1 \le i \le M$) och $D_j = 2$ för alla $j$ ($M + 1 \le j \le N$). Dessutom överstiger beloppet av de givna heltalen i Indata $1, 2, 3$ inte $1000000000 (= 10^9)$. Observera att i Indata $4, 5$ får de givna heltalen eventuellt inte plats inom intervallet för ett $32$-bitars heltal med tecken.

Utdata

Utdata består av $Q$ rader.

På den $i$-te raden ($1 \le i \le Q$) ska du skriva ut ett heltal som representerar positionen för den $i$-te viktiga personen $T$ sekunder efter att kungen gav ordern. Det garanteras av villkoren i problemtexten att detta värde är ett heltal.

Exempel

Indata 1

5 5 3
-8 1
-4 2
-2 2
4 2
10 1
1
3
5

Utdata 1

-6
-6
15

Indata 2

7 18 5
-100 1
-56 2
-34 1
-30 1
-22 1
-4 2
18 2
1
3
4
5
7

Utdata 2

-82
-16
-13
-13
0