레이팅 미적용JOI 国には東西に走る 1 本の十分に長い道路がある.JOI 国の王宮が道路沿いにあり,JOI 国における道路沿いの位置は整数 A で表される.A = 0 のときは王宮の位置を表す.A > 0 のときは,王宮から東へ A メートル進んだ位置を表す.A
JOI 国の道路沿いには N 軒の家があり,家には西から順に 1 から N までの番号が付けられている.JOI 国には N 人の国民がいて,国民には 1 から N までの番号が付けられている.家 i には国民 i が住んでいる.家 i の位置は 0 でない偶数 A i で表される.A 1 , ..., A N は全て異なる.
JOI 国では,近年国民の運動不足が問題になっている.国民の健康が気になった JOI 国の王様は,国民全員に散歩をする命令を出した.王様が命令を出すと,全ての国民は一斉に東向きまたは西向きに歩き始める.それぞれの国民がどちらの向きに歩き始めるかは,国民ごとに決まっている.全ての国民は,歩くときは 1 秒あたり 1 メートルの速度で歩く.
JOI 国の国民は皆おしゃべりが大好きである.散歩の途中にほかの国民に出会うと,その場所で立ち止まって世間話を始めてしまう.すでに立ち止まっている国民に出会った場合も同様である.一度立ち止まった国民は,再び歩き出すことはない.
JOI 国には Q 人の重要人物がいる.JOI 国の王様は,命令が出されてから T 秒後の,Q 人の重要人物の位置を把握しておきたい.命令が出されてから T 秒後の,Q 人の重要人物の位置を求めるプログラムを作成せよ.
入力は,1 + N + Q 行からなる.
1 行目には,3 つの整数 N,T,Q (1 ≦ N ≦ 100000 (= 10 5 ), 0 ≦ T ≦ 10 18 , 1 ≦ Q ≦ 1000,1 ≦ Q ≦ N) が空白を区切りとして書かれている.これは,JOI 国に家が N 軒あり,王様が命令を出してから T 秒後の,Q 人の重要人物の位置を把握しておきたいことを表す.
続く N 行のうち i 行目には,2 つの整数 A i , D i (-10 18 ≦ A i ≦ 10 18 , A i は 0 でない偶数, 1 ≦ D i ≦ 2) が空白を区切りとして書かれている.A i は家 i の位置を表す偶数である.すべての i (1 ≦ i ≦ N - 1) について,A i i+1 を満たす.D i は命令が出された後に国民 i が歩き始める方向を表す.D i = 1 のときは国民 i は東向きに歩き始める.D i = 2 のときは国民 i は西向きに歩き始める.
続く Q 行のうち i 行目には,整数 X i (1 ≦ X i ≦ N) が書かれている.これは,i 番目の重要人物が家 X i に住んでいることを表す.すべての i (1 ≦ i ≦ Q - 1) について,X i i+1 を満たす.
与えられる 5 つの入力データのうち,入力 1 では N ≦ 100,T ≦ 10000を満たす.また,入力 2 では N ≦ 5000 を満たす.また,入力 3 では,ある整数 M (1 ≦ M ≦ N - 1) があって,すべての i (1 ≦ i ≦ M) について D i = 1,すべての j (M + 1 ≦ j ≦ N) について D j = 2 を満たす.また,入力 1,2,3 では,入力に与えられる整数の絶対値は 1000000000 (= 10 9 ) を超えない.入力 4,5 では,与えられる整数が 32 ビット符号付き整数の範囲に収まらないことに注意せよ.
出力は Q 行からなる.
i 行目 (1 ≦ i ≦ Q) には,王様が命令を出してから T 秒後の,i 番目の重要人物の位置を表す整数を出力せよ.この値が整数であることは,問題文の条件より保証されている.
5 5 3
-8 1
-4 2
-2 2
4 2
10 1
1
3
5-6
-6
15