Nel Regno di JOI c'è $1$ strada sufficientemente lunga che corre da est a ovest. Il palazzo reale del Regno di JOI si trova lungo la strada, e una posizione lungo la strada nel Regno di JOI è rappresentata da un intero $A$. Quando $A = 0$, rappresenta la posizione del palazzo reale. Quando $A > 0$, rappresenta la posizione situata $A$ metri a est del palazzo reale. Quando $A < 0$, rappresenta la posizione situata $-A$ metri a ovest del palazzo reale.

Lungo la strada del Regno di JOI ci sono $N$ case, numerate da $1$ a $N$ in ordine da ovest a est. Nel Regno di JOI ci sono $N$ cittadini, numerati da $1$ a $N$. Nella casa $i$ abita il cittadino $i$. La posizione della casa $i$ è rappresentata da un intero pari diverso da $0$, $A_i$. Tutti gli $A_1, \dots, A_N$ sono distinti.

Nel Regno di JOI, negli ultimi anni la mancanza di esercizio fisico dei cittadini è diventata un problema. Preoccupato per la salute dei cittadini, il Re del Regno di JOI ha emanato l'ordine a tutti i cittadini di fare una passeggiata. Non appena il Re emana l'ordine, tutti i cittadini iniziano simultaneamente a camminare verso est oppure verso ovest. La direzione in cui ciascun cittadino inizia a camminare è prestabilita per ogni cittadino. Tutti i cittadini, quando camminano, procedono a una velocità di $1$ metro per $1$ secondo.

Tutti i cittadini del Regno di JOI adorano chiacchierare. Se durante la passeggiata incontrano un altro cittadino, si fermano in quel punto e iniziano a chiacchierare. Lo stesso vale nel caso in cui incontrino un cittadino che si è già fermato. Una volta che un cittadino si è fermato, non riprende più a camminare.

Nel Regno di JOI ci sono $Q$ persone importanti. Il Re del Regno di JOI vuole conoscere le posizioni delle $Q$ persone importanti $T$ secondi dopo l'emanazione dell'ordine. Scrivi un programma per trovare le posizioni delle $Q$ persone importanti $T$ secondi dopo l'emanazione dell'ordine.

Input

L'input è composto da $1 + N + Q$ righe.

Sulla $1$ª riga sono scritti $3$ interi $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$) separati da spazi. Questo indica che nel Regno di JOI ci sono $N$ case e che il Re vuole conoscere le posizioni delle $Q$ persone importanti $T$ secondi dopo aver emanato l'ordine.

Sulla $i$-esima riga delle successive $N$ righe sono scritti $2$ interi $A_i, D_i$ ($-10^{18} \le A_i \le 10^{18}$, $A_i$ è un intero pari diverso da $0$, $1 \le D_i \le 2$) separati da uno spazio. $A_i$ è un intero pari che rappresenta la posizione della casa $i$. Per ogni $i$ ($1 \le i \le N - 1$), vale $A_i < A_{i+1}$. $D_i$ rappresenta la direzione in cui il cittadino $i$ inizia a camminare dopo l'emanazione dell'ordine. Quando $D_i = 1$, il cittadino $i$ inizia a camminare verso est. Quando $D_i = 2$, il cittadino $i$ inizia a camminare verso ovest.

Sulla $i$-esima riga delle successive $Q$ righe è scritto un intero $X_i$ ($1 \le X_i \le N$). Questo indica che la $i$-esima persona importante abita nella casa $X_i$. Per ogni $i$ ($1 \le i \le Q - 1$), vale $X_i < X_{i+1}$.

Tra i $5$ dati di input forniti, nell'input $1$ vale $N \le 100, T \le 10000$. Inoltre, nell'input $2$ vale $N \le 5000$. Inoltre, nell'input $3$ esiste un intero $M$ ($1 \le M \le N - 1$) tale che per ogni $i$ ($1 \le i \le M$) vale $D_i = 1$ e per ogni $j$ ($M + 1 \le j \le N$) vale $D_j = 2$. Inoltre, negli input $1, 2, 3$, il valore assoluto degli interi forniti in input non supera $1000000000 (= 10^9)$. Si noti che negli input $4, 5$, gli interi forniti potrebbero non rientrare nell'intervallo degli interi con segno a $32$ bit.

Output

L'output è composto da $Q$ righe.

Sulla $i$-esima riga ($1 \le i \le Q$), stampa un intero che rappresenta la posizione della $i$-esima persona importante $T$ secondi dopo che il Re ha emanato l'ordine. Dalle condizioni del testo del problema è garantito che questo valore sia un intero.

Esempi

Input 1

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

Output 1

-6
-6
15

Input 2

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

Output 2

-82
-16
-13
-13
0