Í JOI-konungsríkinu er $1$ nægilega langur vegur sem liggur frá austri til vesturs. Konungshöll JOI-konungsríkisins stendur við veginn, og staðsetning við veginn í JOI-konungsríkinu er táknuð með heiltölu $A$. Þegar $A = 0$ táknar það staðsetningu konungshallarinnar. Þegar $A > 0$ táknar það staðsetninguna $A$ metrum austan við konungshöllina. Þegar $A < 0$ táknar það staðsetninguna $-A$ metrum vestan við konungshöllina.

Meðfram veginum í JOI-konungsríkinu eru $N$ hús, og húsin eru númeruð frá $1$ til $N$ í röð frá vestri til austurs. Í JOI-konungsríkinu eru $N$ þegnar, númeraðir frá $1$ til $N$. Í húsi $i$ býr þegn $i$. Staðsetning húss $i$ er táknuð með sléttri tölu $A_i$ sem er ekki $0$. Allar tölurnar $A_1, \dots, A_N$ eru ólíkar.

Í JOI-konungsríkinu hefur hreyfingarleysi þegnanna orðið vandamál á síðustu árum. Konungur JOI-konungsríkisins, sem hafði áhyggjur af heilsu þegnanna, gaf öllum þegnum skipun um að fara í göngutúr. Um leið og konungurinn gefur skipunina leggja allir þegnar samtímis af stað gangandi annaðhvort í austur eða vestur. Í hvaða átt hver þegn leggur af stað er ákveðið fyrir fram fyrir hvern þegn. Allir þegnar ganga á hraðanum $1$ metri á $1$ sekúndu þegar þeir ganga.

Allir þegnar JOI-konungsríkisins elska að spjalla. Ef þeir hitta annan þegn á göngunni nema þeir staðar á þeim stað og byrja að spjalla. Hið sama gildir ef þeir hitta þegn sem hefur þegar numið staðar. Þegn sem hefur einu sinni numið staðar leggur aldrei af stað aftur.

Í JOI-konungsríkinu eru $Q$ mikilvægir einstaklingar. Konungur JOI-konungsríkisins vill vita staðsetningar þessara $Q$ mikilvægu einstaklinga $T$ sekúndum eftir að skipunin er gefin. Skrifið forrit til að finna staðsetningar $Q$ mikilvægu einstaklinganna $T$ sekúndum eftir að skipunin er gefin.

Inntak

Inntakið samanstendur af $1 + N + Q$ línum.

Á $1$. línu standa $3$ heiltölur $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$) aðskildar með bilum. Þetta gefur til kynna að í JOI-konungsríkinu séu $N$ hús og að konungurinn vilji vita staðsetningar $Q$ mikilvægu einstaklinganna $T$ sekúndum eftir að hann gefur skipunina.

Á $i$-tu línu af næstu $N$ línum standa $2$ heiltölur $A_i, D_i$ ($-10^{18} \le A_i \le 10^{18}$, $A_i$ er slétt tala önnur en $0$, $1 \le D_i \le 2$) aðskildar með bili. $A_i$ er slétt tala sem táknar staðsetningu húss $i$. Fyrir öll $i$ ($1 \le i \le N - 1$) gildir $A_i < A_{i+1}$. $D_i$ táknar áttina sem þegn $i$ leggur af stað í eftir að skipunin er gefin. Þegar $D_i = 1$ leggur þegn $i$ af stað í austur. Þegar $D_i = 2$ leggur þegn $i$ af stað í vestur.

Á $i$-tu línu af næstu $Q$ línum stendur heiltala $X_i$ ($1 \le X_i \le N$). Þetta gefur til kynna að $i$-ti mikilvægi einstaklingurinn búi í húsi $X_i$. Fyrir öll $i$ ($1 \le i \le Q - 1$) gildir $X_i < X_{i+1}$.

Af þeim $5$ inntaksgagnasettum sem gefin eru uppfyllir inntak $1$ skilyrðin $N \le 100, T \le 10000$. Einnig uppfyllir inntak $2$ skilyrðið $N \le 5000$. Ennfremur gildir í inntaki $3$ að til er heiltala $M$ ($1 \le M \le N - 1$) þannig að fyrir öll $i$ ($1 \le i \le M$) gildir $D_i = 1$ og fyrir öll $j$ ($M + 1 \le j \le N$) gildir $D_j = 2$. Að auki er tölugildi heiltalnanna sem gefnar eru í inntökum $1, 2, 3$ ekki hærra en $1000000000 (= 10^9)$. Athugið að í inntökum $4, 5$ rúmast gefnu heiltölurnar ekki endilega innan sviðs $32$-bita heiltölu með formerki.

Úttak

Úttakið samanstendur af $Q$ línum.

Á $i$-tu línu ($1 \le i \le Q$) skal prenta heiltölu sem táknar staðsetningu $i$-ta mikilvæga einstaklingsins $T$ sekúndum eftir að konungurinn gaf skipunina. Skilyrði dæmisins tryggja að þetta gildi sé heiltala.

Dæmi

Inntak 1

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

Úttak 1

-6
-6
15

Inntak 2

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

Úttak 2

-82
-16
-13
-13
0