Dans le royaume de JOI, il y a $1$ route suffisamment longue qui s'étend d'est en ouest. Le palais royal du royaume de JOI se trouve le long de cette route, et une position le long de la route dans le royaume de JOI est représentée par un entier $A$. Lorsque $A = 0$, cela représente la position du palais royal. Lorsque $A > 0$, cela représente la position située à $A$ mètres à l'est du palais royal. Lorsque $A < 0$, cela représente la position située à $-A$ mètres à l'ouest du palais royal.

Il y a $N$ maisons le long de la route dans le royaume de JOI, et ces maisons sont numérotées de $1$ à $N$ dans l'ordre d'ouest en est. Il y a $N$ citoyens dans le royaume de JOI, numérotés de $1$ à $N$. Le citoyen $i$ habite dans la maison $i$. La position de la maison $i$ est représentée par un entier pair non nul $A_i$. Tous les $A_1, \dots, A_N$ sont distincts.

Dans le royaume de JOI, le manque d'exercice des citoyens est récemment devenu un problème. Soucieux de la santé des citoyens, le roi du royaume de JOI a donné l'ordre à tous les citoyens de faire une promenade. Dès que le roi donne l'ordre, tous les citoyens commencent simultanément à marcher soit vers l'est, soit vers l'ouest. La direction dans laquelle chaque citoyen commence à marcher est fixée à l'avance pour chacun d'eux. Lorsqu'ils marchent, tous les citoyens se déplacent à la vitesse de $1$ mètre par $1$ seconde.

Tous les citoyens du royaume de JOI adorent bavarder. Si un citoyen rencontre un autre citoyen au cours de sa promenade, il s'arrête sur place et commence à discuter. Il en va de même s'il rencontre un citoyen qui s'est déjà arrêté. Une fois qu'un citoyen s'est arrêté, il ne recommence jamais à marcher.

Il y a $Q$ personnalités importantes dans le royaume de JOI. Le roi du royaume de JOI souhaite connaître la position de ces $Q$ personnalités importantes $T$ secondes après que l'ordre a été donné. Écrivez un programme pour déterminer la position des $Q$ personnalités importantes $T$ secondes après que l'ordre a été donné.

Entrée

L'entrée se compose de $1 + N + Q$ lignes.

Sur la $1$-re ligne sont écrits $3$ entiers $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$) séparés par des espaces. Cela indique qu'il y a $N$ maisons dans le royaume de JOI et que le roi souhaite connaître la position des $Q$ personnalités importantes $T$ secondes après avoir donné l'ordre.

Sur la $i$-e ligne des $N$ lignes suivantes sont écrits $2$ entiers $A_i, D_i$ ($-10^{18} \le A_i \le 10^{18}$, $A_i$ est un entier pair non nul, $1 \le D_i \le 2$) séparés par un espace. $A_i$ est un entier pair représentant la position de la maison $i$. Pour tout $i$ ($1 \le i \le N - 1$), on a $A_i < A_{i+1}$. $D_i$ représente la direction dans laquelle le citoyen $i$ commence à marcher une fois l'ordre donné. Lorsque $D_i = 1$, le citoyen $i$ commence à marcher vers l'est. Lorsque $D_i = 2$, le citoyen $i$ commence à marcher vers l'ouest.

Sur la $i$-e ligne des $Q$ lignes suivantes est écrit un entier $X_i$ ($1 \le X_i \le N$). Cela indique que la $i$-e personnalité importante habite dans la maison $X_i$. Pour tout $i$ ($1 \le i \le Q - 1$), on a $X_i < X_{i+1}$.

Parmi les $5$ jeux de données d'entrée fournis, l'entrée $1$ satisfait $N \le 100, T \le 10000$. De plus, l'entrée $2$ satisfait $N \le 5000$. En outre, dans l'entrée $3$, il existe un entier $M$ ($1 \le M \le N - 1$) tel que $D_i = 1$ pour tout $i$ ($1 \le i \le M$) et $D_j = 2$ pour tout $j$ ($M + 1 \le j \le N$). Par ailleurs, dans les entrées $1, 2, 3$, la valeur absolue des entiers donnés en entrée ne dépasse pas $1000000000 (= 10^9)$. Notez que dans les entrées $4, 5$, les entiers donnés peuvent ne pas tenir dans un entier signé sur $32$ bits.

Sortie

La sortie se compose de $Q$ lignes.

Sur la $i$-e ligne ($1 \le i \le Q$), affichez un entier représentant la position de la $i$-e personnalité importante $T$ secondes après que le roi a donné l'ordre. Les conditions de l'énoncé garantissent que cette valeur est un entier.

Exemples

Entrée 1

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

Sortie 1

-6
-6
15

Entrée 2

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

Sortie 2

-82
-16
-13
-13
0