JOI патшалығында шығыстан батысқа қарай созылып жатқан жеткілікті ұзын $1$ жол бар. JOI патшалығының патша сарайы осы жолдың бойында орналасқан, ал JOI патшалығындағы жол бойындағы орын $A$ бүтін санымен өрнектеледі. $A = 0$ болғанда, ол патша сарайының орнын білдіреді. $A > 0$ болғанда, ол патша сарайынан шығысқа қарай $A$ метр жүргендегі орынды білдіреді. $A < 0$ болғанда, ол патша сарайынан батысқа қарай $-A$ метр жүргендегі орынды білдіреді.

JOI патшалығының жол бойында $N$ үй бар, және үйлер батыстан шығысқа қарай ретімен $1$-ден $N$-ге дейін нөмірленген. JOI патшалығында $N$ тұрғын бар, олар $1$-ден $N$-ге дейін нөмірленген. $i$-үйде $i$-тұрғын тұрады. $i$-үйдің орны $0$-ге тең емес жұп сан $A_i$ арқылы беріледі. Барлық $A_1, \dots, A_N$ сандары әртүрлі.

Соңғы жылдары JOI патшалығында тұрғындардың аз қозғалуы мәселеге айналды. Тұрғындардың денсаулығына алаңдаған JOI патшалығының патшасы барлық тұрғындарға серуендеу туралы бұйрық берді. Патша бұйрық берген сәтте барлық тұрғындар бір мезгілде шығысқа немесе батысқа қарай жүре бастайды. Әрбір тұрғынның қай бағытта жүре бастайтыны әр тұрғын үшін алдын ала белгіленген. Барлық тұрғындар жүрген кезде $1$ секундта $1$ метр жылдамдықпен жүреді.

JOI патшалығының барлық тұрғындары әңгімелескенді өте жақсы көреді. Егер серуен барысында басқа бір тұрғынды кездестірсе, олар сол жерде тоқтап, әңгіме айта бастайды. Алдын ала тоқтап тұрған тұрғынды кездестірген жағдайда да дәл солай болады. Бір рет тоқтаған тұрғын қайтадан жүре бастамайды.

JOI патшалығында $Q$ маңызды тұлға бар. JOI патшалығының патшасы бұйрық берілгеннен кейін $T$ секунд өткен соң осы $Q$ маңызды тұлғаның қай жерде екенін біліп отырғысы келеді. Бұйрық берілгеннен кейін $T$ секунд өткен соң $Q$ маңызды тұлғаның орнын табатын программа жазыңыз.

Кіріс деректер

Кіріс деректер $1 + N + Q$ жолдан тұрады.

$1$-ші жолда бос орын арқылы бөлінген $3$ бүтін сан $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$) жазылған. Бұл JOI патшалығында $N$ үй бар екенін және патша бұйрық бергеннен кейін $T$ секунд өткен соң $Q$ маңызды тұлғаның орнын білгісі келетінін білдіреді.

Келесі $N$ жолдың $i$-ші жолында бос орын арқылы бөлінген $2$ бүтін сан $A_i, D_i$ ($-10^{18} \le A_i \le 10^{18}$, $A_i$ — $0$-ге тең емес жұп сан, $1 \le D_i \le 2$) жазылған. $A_i$ — $i$-үйдің орнын білдіретін жұп сан. Барлық $i$ ($1 \le i \le N - 1$) үшін $A_i < A_{i+1}$ шарты орындалады. $D_i$ бұйрық берілгеннен кейін $i$-тұрғынның жүре бастайтын бағытын білдіреді. $D_i = 1$ болғанда, $i$-тұрғын шығысқа қарай жүре бастайды. $D_i = 2$ болғанда, $i$-тұрғын батысқа қарай жүре бастайды.

Келесі $Q$ жолдың $i$-ші жолында $X_i$ ($1 \le X_i \le N$) бүтін саны жазылған. Бұл $i$-ші маңызды тұлғаның $X_i$-үйде тұратынын білдіреді. Барлық $i$ ($1 \le i \le Q - 1$) үшін $X_i < X_{i+1}$ шарты орындалады.

Берілген $5$ кіріс деректер жиынының ішінде $1$-кірісте $N \le 100, T \le 10000$ шарттары орындалады. Сондай-ақ $2$-кірісте $N \le 5000$ шарты орындалады. Ал $3$-кірісте барлық $i$ ($1 \le i \le M$) үшін $D_i = 1$ және барлық $j$ ($M + 1 \le j \le N$) үшін $D_j = 2$ болатындай бір $M$ ($1 \le M \le N - 1$) бүтін саны табылады. Сонымен қатар, $1, 2, 3$-кірістерде кірісте берілген бүтін сандардың абсолюттік шамасы $1000000000 (= 10^9)$ мәнінен аспайды. $4, 5$-кірістерде берілген бүтін сандар $32$ биттік таңбалы бүтін сандар диапазонына сыймауы мүмкін екеніне назар аударыңыз.

Шығыс деректер

Шығыс деректер $Q$ жолдан тұрады.

$i$-ші жолға ($1 \le i \le Q$) патша бұйрық бергеннен кейін $T$ секунд өткен соң $i$-ші маңызды тұлғаның орнын білдіретін бүтін санды шығарыңыз. Бұл мәннің бүтін сан болатыны есеп шартымен кепілдендірілген.

Мысалдар

Кіріс 1

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

Шығыс 1

-6
-6
15

Кіріс 2

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

Шығыс 2

-82
-16
-13
-13
0