JOI-kuningaskunnassa on $1$ riittävän pitkä itä–länsisuuntainen tie. JOI-kuningaskunnan kuninkaanlinna sijaitsee tien varrella, ja sijaintia tien varrella JOI-kuningaskunnassa kuvataan kokonaisluvulla $A$. Kun $A = 0$, se tarkoittaa kuninkaanlinnan sijaintia. Kun $A > 0$, se tarkoittaa sijaintia $A$ metriä kuninkaanlinnasta itään. Kun $A < 0$, se tarkoittaa sijaintia $-A$ metriä kuninkaanlinnasta länteen.

JOI-kuningaskunnan tien varrella on $N$ taloa, ja talot on numeroitu lännestä itään järjestyksessä luvuilla $1$:stä $N$:ään. JOI-kuningaskunnassa on $N$ kansalaista, jotka on numeroitu luvuilla $1$:stä $N$:ään. Talossa $i$ asuu kansalainen $i$. Talon $i$ sijaintia kuvaa nollasta poikkeava parillinen luku $A_i$. Kaikki luvut $A_1, \dots, A_N$ ovat keskenään eri suuria.

JOI-kuningaskunnassa kansalaisten liikunnan puutteesta on viime vuosina tullut ongelma. Kansalaisten terveydestä huolestunut JOI-kuningaskunnan kuningas antoi kaikille kansalaisille käskyn lähteä kävelylle. Kun kuningas antaa käskyn, kaikki kansalaiset lähtevät yhtä aikaa kävelemään joko itään tai länteen. Kunkin kansalaisen kävelysuunta on määrätty kansalaiskohtaisesti. Kaikki kansalaiset kävelevät vauhdilla $1$ metri $1$ sekunnissa.

Kaikki JOI-kuningaskunnan kansalaiset pitävät kovasti juttelemisesta. Jos he kohtaavat kävelyn aikana toisen kansalaisen, he pysähtyvät sille paikalle ja alkavat jutella kuulumisia. Sama pätee myös silloin, kun he kohtaavat jo pysähtyneen kansalaisen. Kerran pysähtynyt kansalainen ei enää lähde uudelleen liikkeelle.

JOI-kuningaskunnassa on $Q$ tärkeää henkilöä. JOI-kuningaskunnan kuningas haluaa tietää näiden $Q$ tärkeän henkilön sijainnit $T$ sekunnin kuluttua käskyn antamisesta. Kirjoita ohjelma, joka selvittää $Q$ tärkeän henkilön sijainnit $T$ sekunnin kuluttua käskyn antamisesta.

Syöte

Syöte koostuu $1 + N + Q$ rivistä.

$1$. rivillä on $3$ välilyönnein erotettua kokonaislukua $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$). Tämä tarkoittaa, että JOI-kuningaskunnassa on $N$ taloa ja kuningas haluaa tietää $Q$ tärkeän henkilön sijainnit $T$ sekunnin kuluttua käskyn antamisesta.

Seuraavien $N$ rivin $i$:nnellä rivillä on $2$ välilyönnillä erotettua kokonaislukua $A_i, D_i$ ($-10^{18} \le A_i \le 10^{18}$, $A_i$ on nollasta poikkeava parillinen luku, $1 \le D_i \le 2$). $A_i$ on talon $i$ sijaintia kuvaava parillinen luku. Kaikilla $i$ ($1 \le i \le N - 1$) pätee $A_i < A_{i+1}$. $D_i$ ilmaisee suunnan, johon kansalainen $i$ lähtee kävelemään käskyn antamisen jälkeen. Kun $D_i = 1$, kansalainen $i$ lähtee kävelemään itään. Kun $D_i = 2$, kansalainen $i$ lähtee kävelemään länteen.

Seuraavien $Q$ rivin $i$:nnellä rivillä on kokonaisluku $X_i$ ($1 \le X_i \le N$). Tämä tarkoittaa, että $i$:s tärkeä henkilö asuu talossa $X_i$. Kaikilla $i$ ($1 \le i \le Q - 1$) pätee $X_i < X_{i+1}$.

Annetuista $5$ syötetiedostosta syötteessä $1$ pätee $N \le 100, T \le 10000$. Lisäksi syötteessä $2$ pätee $N \le 5000$. Syötteessä $3$ on olemassa sellainen kokonaisluku $M$ ($1 \le M \le N - 1$), että kaikilla $i$ ($1 \le i \le M$) pätee $D_i = 1$ ja kaikilla $j$ ($M + 1 \le j \le N$) pätee $D_j = 2$. Lisäksi syötteissä $1, 2, 3$ syötteessä annettujen kokonaislukujen itseisarvo on korkeintaan $1000000000 (= 10^9)$. Huomaa, että syötteissä $4, 5$ annetut kokonaisluvut eivät välttämättä mahdu $32$-bittisen etumerkillisen kokonaisluvun arvoalueelle.

Tuloste

Tuloste koostuu $Q$ rivistä.

Tulosta $i$:nnelle riville ($1 \le i \le Q$) kokonaisluku, joka ilmaisee $i$:nnen tärkeän henkilön sijainnin $T$ sekunnin kuluttua siitä, kun kuningas antoi käskyn. Tehtävänannon ehdot takaavat, että tämä arvo on kokonaisluku.

Esimerkit

Syöte 1

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

Tuloste 1

-6
-6
15

Syöte 2

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

Tuloste 2

-82
-16
-13
-13
0