I kongeriket JOI er det $1$ tilstrekkelig lang vei som går fra øst til vest. Det kongelige slottet i kongeriket JOI ligger langs veien, og en posisjon langs veien i kongeriket JOI representeres av et heltall $A$. Når $A = 0$, representerer det posisjonen til det kongelige slottet. Når $A > 0$, representerer det posisjonen $A$ meter øst for det kongelige slottet. Når $A < 0$, representerer det posisjonen $-A$ meter vest for det kongelige slottet.

Langs veien i kongeriket JOI ligger det $N$ hus, og husene er nummerert fra $1$ til $N$ i rekkefølge fra vest til øst. Det er $N$ innbyggere i kongeriket JOI, nummerert fra $1$ til $N$. I hus $i$ bor innbygger $i$. Posisjonen til hus $i$ er representert av et partall $A_i$ ulikt $0$. Alle $A_1, \dots, A_N$ er forskjellige.

I kongeriket JOI har mangel på mosjon blant innbyggerne blitt et problem i de senere årene. Bekymret for innbyggernes helse ga kongen av kongeriket JOI ordre til alle innbyggerne om å gå en tur. Når kongen gir ordren, begynner alle innbyggerne samtidig å gå enten østover eller vestover. Hvilken retning hver innbygger begynner å gå i, er bestemt på forhånd for hver enkelt innbygger. Når innbyggerne går, går alle med en fart på $1$ meter per $1$ sekund.

Alle innbyggerne i kongeriket JOI elsker å slå av en prat. Hvis de møter en annen innbygger underveis på turen, stopper de på stedet og begynner å småprate. Det samme gjelder hvis de møter en innbygger som allerede har stoppet. En innbygger som først har stoppet, begynner aldri å gå igjen.

Det er $Q$ viktige personer i kongeriket JOI. Kongen av kongeriket JOI ønsker å ha oversikt over posisjonene til de $Q$ viktige personene $T$ sekunder etter at ordren ble gitt. Skriv et program som finner posisjonene til de $Q$ viktige personene $T$ sekunder etter at ordren ble gitt.

Inndata

Inndataene består av $1 + N + Q$ linjer.

På den $1$. linjen står $3$ heltall $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$) atskilt med mellomrom. Dette angir at det er $N$ hus i kongeriket JOI, og at kongen ønsker å vite posisjonene til de $Q$ viktige personene $T$ sekunder etter at han har gitt ordren.

På den $i$-te linjen av de neste $N$ linjene står $2$ heltall $A_i, D_i$ ($-10^{18} \le A_i \le 10^{18}$, $A_i$ er et partall ulikt $0$, $1 \le D_i \le 2$) atskilt med mellomrom. $A_i$ er et partall som representerer posisjonen til hus $i$. For alle $i$ ($1 \le i \le N - 1$) gjelder $A_i < A_{i+1}$. $D_i$ representerer retningen innbygger $i$ begynner å gå i etter at ordren er gitt. Når $D_i = 1$, begynner innbygger $i$ å gå østover. Når $D_i = 2$, begynner innbygger $i$ å gå vestover.

På den $i$-te linjen av de neste $Q$ linjene står et heltall $X_i$ ($1 \le X_i \le N$). Dette angir at den $i$-te viktige personen bor i hus $X_i$. For alle $i$ ($1 \le i \le Q - 1$) gjelder $X_i < X_{i+1}$.

Blant de $5$ gitte inndatasettene oppfyller Inndata $1$ betingelsene $N \le 100, T \le 10000$. Videre oppfyller Inndata $2$ betingelsen $N \le 5000$. I Inndata $3$ finnes det et heltall $M$ ($1 \le M \le N - 1$) slik at $D_i = 1$ for alle $i$ ($1 \le i \le M$) og $D_j = 2$ for alle $j$ ($M + 1 \le j \le N$). Dessuten overstiger ikke absoluttverdien av heltallene gitt i Inndata $1, 2, 3$ verdien $1000000000 (= 10^9)$. Merk at i Inndata $4, 5$ vil de gitte heltallene kanskje ikke få plass innenfor området til et $32$-biters heltall med fortegn.

Utdata

Utdataene består av $Q$ linjer.

På den $i$-te linjen ($1 \le i \le Q$) skal du skrive ut et heltall som representerer posisjonen til den $i$-te viktige personen $T$ sekunder etter at kongen ga ordren. Det er garantert av betingelsene i oppgaveteksten at denne verdien er et heltall.

Eksempler

Inndata 1

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

Utdata 1

-6
-6
15

Inndata 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