Di Kerajaan JOI, terdapat $1$ jalan yang cukup panjang yang membentang dari timur ke barat. Istana kerajaan Kerajaan JOI terletak di tepi jalan tersebut, dan posisi di sepanjang jalan di Kerajaan JOI dinyatakan dengan bilangan bulat $A$. Ketika $A = 0$, itu menyatakan posisi istana kerajaan. Ketika $A > 0$, itu menyatakan posisi sejauh $A$ meter ke arah timur dari istana kerajaan. Ketika $A < 0$, itu menyatakan posisi sejauh $-A$ meter ke arah barat dari istana kerajaan.

Terdapat $N$ rumah di sepanjang jalan di Kerajaan JOI, dan rumah-rumah tersebut diberi nomor dari $1$ hingga $N$ secara berurutan dari barat ke timur. Terdapat $N$ warga di Kerajaan JOI, yang diberi nomor dari $1$ hingga $N$. Warga $i$ tinggal di rumah $i$. Posisi rumah $i$ dinyatakan oleh bilangan bulat genap tak nol $A_i$. Semua $A_1, \dots, A_N$ berbeda satu sama lain.

Di Kerajaan JOI, kurangnya olahraga di kalangan warga belakangan ini menjadi masalah. Karena mengkhawatirkan kesehatan para warga, Raja Kerajaan JOI mengeluarkan perintah kepada seluruh warga untuk berjalan-jalan. Begitu Raja mengeluarkan perintah, semua warga secara serentak mulai berjalan ke arah timur atau ke arah barat. Arah mulai berjalan untuk masing-masing warga sudah ditentukan untuk setiap warga. Semua warga berjalan dengan kecepatan $1$ meter per $1$ detik.

Semua warga Kerajaan JOI sangat suka mengobrol. Jika seorang warga bertemu dengan warga lain di tengah perjalanan, mereka akan berhenti di tempat itu dan mulai mengobrol. Hal yang sama juga berlaku jika mereka bertemu dengan warga yang sudah berhenti. Warga yang sudah berhenti satu kali tidak akan mulai berjalan lagi.

Terdapat $Q$ orang penting di Kerajaan JOI. Raja Kerajaan JOI ingin mengetahui posisi dari $Q$ orang penting tersebut $T$ detik setelah perintah dikeluarkan. Buatlah program untuk mencari posisi dari $Q$ orang penting tersebut $T$ detik setelah perintah dikeluarkan.

Masukan

Masukan terdiri dari $1 + N + Q$ baris.

Pada baris ke-$1$, tertulis $3$ bilangan bulat $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$) yang dipisahkan oleh spasi. Ini menyatakan bahwa terdapat $N$ rumah di Kerajaan JOI, dan Raja ingin mengetahui posisi dari $Q$ orang penting $T$ detik setelah mengeluarkan perintah.

Pada baris ke-$i$ dari $N$ baris berikutnya, tertulis $2$ bilangan bulat $A_i, D_i$ ($-10^{18} \le A_i \le 10^{18}$, $A_i$ adalah bilangan genap tak nol, $1 \le D_i \le 2$) yang dipisahkan oleh spasi. $A_i$ adalah bilangan genap yang menyatakan posisi rumah $i$. Untuk semua $i$ ($1 \le i \le N - 1$), berlaku $A_i < A_{i+1}$. $D_i$ menyatakan arah warga $i$ mulai berjalan setelah perintah dikeluarkan. Ketika $D_i = 1$, warga $i$ mulai berjalan ke arah timur. Ketika $D_i = 2$, warga $i$ mulai berjalan ke arah barat.

Pada baris ke-$i$ dari $Q$ baris berikutnya, tertulis sebuah bilangan bulat $X_i$ ($1 \le X_i \le N$). Ini menyatakan bahwa orang penting ke-$i$ tinggal di rumah $X_i$. Untuk semua $i$ ($1 \le i \le Q - 1$), berlaku $X_i < X_{i+1}$.

Di antara $5$ data masukan yang diberikan, Masukan $1$ memenuhi $N \le 100, T \le 10000$. Selain itu, Masukan $2$ memenuhi $N \le 5000$. Selain itu, pada Masukan $3$, terdapat suatu bilangan bulat $M$ ($1 \le M \le N - 1$) sedemikian sehingga untuk semua $i$ ($1 \le i \le M$) berlaku $D_i = 1$, dan untuk semua $j$ ($M + 1 \le j \le N$) berlaku $D_j = 2$. Lebih lanjut, pada Masukan $1, 2, 3$, nilai mutlak dari bilangan bulat yang diberikan pada masukan tidak melebihi $1000000000 (= 10^9)$. Perhatikan bahwa pada Masukan $4, 5$, bilangan bulat yang diberikan mungkin tidak muat dalam rentang bilangan bulat bertanda $32$-bit.

Keluaran

Keluaran terdiri dari $Q$ baris.

Pada baris ke-$i$ ($1 \le i \le Q$), keluarkan sebuah bilangan bulat yang menyatakan posisi orang penting ke-$i$ pada $T$ detik setelah Raja mengeluarkan perintah. Dijamin oleh kondisi pada soal bahwa nilai ini merupakan bilangan bulat.

Contoh

Masukan 1

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

Keluaran 1

-6
-6
15

Masukan 2

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

Keluaran 2

-82
-16
-13
-13
0