JOI 王國有一條沿東西方向延伸、足夠長的 $1$ 條道路。JOI 王國的王宮位於道路旁，JOI 王國中道路旁的位置以整數 $A$ 表示。當 $A = 0$ 時表示王宮的位置。當 $A > 0$ 時表示從王宮向東前進 $A$ 公尺的位置。當 $A < 0$ 時表示從王宮向西前進 $-A$ 公尺的位置。

JOI 王國的道路旁有 $N$ 棟房子，房子按由西向東的順序從 $1$ 到 $N$ 編號。JOI 王國有 $N$ 名國民，國民從 $1$ 到 $N$ 編號。房子 $i$ 裡住著國民 $i$。房子 $i$ 的位置以非零偶數 $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$ 為非零偶數，$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$ 滿足存在某個整數 $M$（$1 \le M \le N - 1$），使得對於所有 $i$（$1 \le i \le M$）滿足 $D_i = 1$，且對於所有 $j$（$M + 1 \le j \le N$）滿足 $D_j = 2$。此外，在輸入 $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