/ 
Time Limit: 10 sec / Memory Limit: 256 MB
配点： 100 点
問題
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, \ldots, A_N は全て異なる．
JOI 国では，近年国民の運動不足が問題になっている．国民の健康が気になった JOI 国の王様は，国民全員に散歩をする命令を出した．王様が命令を出すと，全ての国民は一斉に東向きまたは西向きに歩き始める．それぞれの国民がどちらの向きに歩き始めるかは，国民ごとに決まっている．全ての国民は，歩くときは 1 秒あたり 1 メートルの速度で歩く．
JOI 国の国民は皆おしゃべりが大好きである．散歩の途中にほかの国民に出会うと，その場所で立ち止まって世間話を始めてしまう．すでに立ち止まっている国民に出会った場合も同様である．一度立ち止まった国民は，再び歩き出すことはない．
JOI 国には Q 人の重要人物がいる．JOI 国の王様は，命令が出されてから T 秒後の，Q 人の重要人物の位置を把握しておきたい．命令が出されてから T 秒後の，Q 人の重要人物の位置を求めるプログラムを作成せよ．
入力
入力は，1 + N + Q 行からなる．
1 行目には，3 つの整数 N，T，Q (1 \leqq N \leqq 100\,000 \ (= 10^5)，0 \leqq T \leqq 10^{18}，1 \leqq Q \leqq 1\,000，1 \leqq Q \leqq N) が空白を区切りとして書かれている．これは，JOI 国に家が N 軒あり，王様が命令を出してから T 秒後の，Q 人の重要人物の位置を把握しておきたいことを表す．
続く N 行のうち i 行目には，2 つの整数 A_i, D_i (-10^{18} \leqq A_i \leqq 10^{18}，A_i は 0 でない偶数，1 \leqq D_i \leqq 2) が空白を区切りとして書かれている．A_i は家 i の位置を表す偶数である．すべての i (1 \leqq i \leqq N - 1) について，A_i < A_{i + 1} を満たす．D_i は命令が出された後に国民 i が歩き始める方向を表す．D_i = 1 のときは国民 i は東向きに歩き始める．D_i = 2 のときは国民 i は西向きに歩き始める．
続く Q 行のうち i 行目には，整数 X_i (1 \leqq X_i \leqq N) が書かれている．これは，i 番目の重要人物が家 X_i に住んでいることを表す．すべての i (1 \leqq i \leqq Q - 1) について，X_i < X_{i + 1} を満たす．
与えられる 5 つの入力データのうち，入力 1 では N \leqq 100，T \leqq 10\,000 を満たす．また，入力 2 では N \leqq 5\,000 を満たす．また，入力 3 では，ある整数 M (1 \leqq M \leqq N - 1) があって，すべての i (1 \leqq i \leqq M) について D_i = 1，すべての j (M + 1 \leqq j \leqq N) について D_j = 2 を満たす．また，入力 1, 2, 3 では，入力に与えられる整数の絶対値は 1\,000\,000\,000 \ (= 10^9) を超えない．入力 4, 5 では，与えられる整数が 32 ビット符号付き整数の範囲に収まらないことに注意せよ．
出力
出力は Q 行からなる．
i 行目 (1 \leqq i \leqq 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