En el Reino de JOI hay $1$ carretera suficientemente larga que va de este a oeste. El palacio real del Reino de JOI se encuentra a lo largo de la carretera, y una posición a lo largo de la carretera en el Reino de JOI se representa mediante un número entero $A$. Cuando $A = 0$, representa la posición del palacio real. Cuando $A > 0$, representa la posición tras avanzar $A$ metros hacia el este desde el palacio real. Cuando $A < 0$, representa la posición tras avanzar $-A$ metros hacia el oeste desde el palacio real.

Hay $N$ casas a lo largo de la carretera en el Reino de JOI, numeradas del $1$ al $N$ en orden de oeste a este. Hay $N$ ciudadanos en el Reino de JOI, numerados del $1$ al $N$. En la casa $i$ vive el ciudadano $i$. La posición de la casa $i$ se representa mediante un número entero par distinto de $0$, $A_i$. Todos los $A_1, \dots, A_N$ son diferentes.

En el Reino de JOI, en los últimos años la falta de ejercicio de los ciudadanos se ha convertido en un problema. Preocupado por la salud de los ciudadanos, el Rey del Reino de JOI dio la orden a todos los ciudadanos de salir a pasear. Cuando el Rey da la orden, todos los ciudadanos comienzan a caminar simultáneamente hacia el este o hacia el oeste. Hacia qué dirección comienza a caminar cada ciudadano está determinado para cada ciudadano. Todos los ciudadanos, cuando caminan, lo hacen a una velocidad de $1$ metro por cada $1$ segundo.

A todos los ciudadanos del Reino de JOI les encanta charlar. Si durante el paseo se encuentran con otro ciudadano, se detienen en ese lugar y se ponen a charlar. Lo mismo ocurre si se encuentran con un ciudadano que ya se ha detenido. Una vez que un ciudadano se detiene, no vuelve a caminar.

En el Reino de JOI hay $Q$ personas importantes. El Rey del Reino de JOI quiere conocer las posiciones de las $Q$ personas importantes $T$ segundos después de haberse dado la orden. Escribe un programa para hallar las posiciones de las $Q$ personas importantes $T$ segundos después de haberse dado la orden.

Entrada

La entrada consta de $1 + N + Q$ líneas.

En la $1$-ª línea están escritos $3$ enteros $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$) separados por espacios. Esto indica que en el Reino de JOI hay $N$ casas y que el Rey quiere conocer las posiciones de las $Q$ personas importantes $T$ segundos después de dar la orden.

En la $i$-ésima línea de las siguientes $N$ líneas están escritos $2$ enteros $A_i, D_i$ ($-10^{18} \le A_i \le 10^{18}$, $A_i$ es un número par distinto de $0$, $1 \le D_i \le 2$) separados por un espacio. $A_i$ es un número par que representa la posición de la casa $i$. Para todo $i$ ($1 \le i \le N - 1$), se cumple $A_i < A_{i+1}$. $D_i$ representa la dirección en la que el ciudadano $i$ comienza a caminar después de darse la orden. Cuando $D_i = 1$, el ciudadano $i$ comienza a caminar hacia el este. Cuando $D_i = 2$, el ciudadano $i$ comienza a caminar hacia el oeste.

En la $i$-ésima línea de las siguientes $Q$ líneas está escrito un entero $X_i$ ($1 \le X_i \le N$). Esto indica que la $i$-ésima persona importante vive en la casa $X_i$. Para todo $i$ ($1 \le i \le Q - 1$), se cumple $X_i < X_{i+1}$.

De los $5$ casos de entrada dados, en la entrada $1$ se cumple $N \le 100, T \le 10000$. Además, en la entrada $2$ se cumple $N \le 5000$. Además, en la entrada $3$ existe un entero $M$ ($1 \le M \le N - 1$) tal que para todo $i$ ($1 \le i \le M$) se cumple $D_i = 1$, y para todo $j$ ($M + 1 \le j \le N$) se cumple $D_j = 2$. Asimismo, en las entradas $1, 2, 3$, el valor absoluto de los enteros dados en la entrada no supera $1000000000 (= 10^9)$. Ten en cuenta que en las entradas $4, 5$, los enteros dados pueden no caber en el rango de un entero con signo de $32$ bits.

Salida

La salida consta de $Q$ líneas.

En la $i$-ésima línea ($1 \le i \le Q$), imprime el entero que representa la posición de la $i$-ésima persona importante $T$ segundos después de que el Rey dé la orden. Las condiciones del enunciado garantizan que este valor es un número entero.

Ejemplos

Entrada 1

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

Salida 1

-6
-6
15

Entrada 2

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

Salida 2

-82
-16
-13
-13
0