JOI 国には東西に走る $1$ 本の十分に長い道路がある．JOI 国の王宮が道路沿いにあり，JOI 国における道路沿いの位置は整数 $A$ で表される．$A = 0$ のときは王宮の位置を表す．$A > 0$ のときは，王宮から東へ $A$ メートル進んだ位置を表す．$A < 0$ のときは，王宮から西へ $-A$ メートル進んだ位置を表す．

JOI 国の道路沿いには $N$ 軒の家があり，家には西から順に $1$ から $N$ までの番号が付けられている．JOI 国には $N$ 人の国民がいて，国民には $1$ から $N$ までの番号が付けられている．家 $i$ には国民 $i$ が住んでいる．家 $i$ の位置は $0$ でない偶数 $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$ は $0$ でない偶数, $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