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