Walking in JOI Kingdom

Time Limit : 8 sec, Memory Limit : 262144 KB

JOI国のお散歩事情 (Walking in JOI Kingdom)

問題

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 でない偶数 Ai で表される.A1, ..., AN は全て異なる.

JOI 国では,近年国民の運動不足が問題になっている.国民の健康が気になった JOI 国の王様は,国民全員に散歩をする命令を出した.王様が命令を出すと,全ての国民は一斉に東向きまたは西向きに歩き始める.それぞれの国民がどちらの向きに歩き始めるかは,国民ごとに決まっている.全ての国民は,歩くときは 1 秒あたり 1 メートルの速度で歩く.

JOI 国の国民は皆おしゃべりが大好きである.散歩の途中にほかの国民に出会うと,その場所で立ち止まって世間話を始めてしまう.すでに立ち止まっている国民に出会った場合も同様である.一度立ち止まった国民は,再び歩き出すことはない.

JOI 国には Q 人の重要人物がいる.JOI 国の王様は,命令が出されてから T 秒後の,Q 人の重要人物の位置を把握しておきたい.命令が出されてから T 秒後の,Q 人の重要人物の位置を求めるプログラムを作成せよ.

入力

入力は,1 + N + Q 行からなる.

1 行目には,3 つの整数 N,T,Q (1 ≦ N ≦ 100000 (= 105), 0 ≦ T ≦ 1018, 1 ≦ Q ≦ 1000,1 ≦ Q ≦ N) が空白を区切りとして書かれている.これは,JOI 国に家が N 軒あり,王様が命令を出してから T 秒後の,Q 人の重要人物の位置を把握しておきたいことを表す.

続く N 行のうち i 行目には,2 つの整数 Ai, Di (-1018 ≦ Ai ≦ 1018, Ai は 0 でない偶数, 1 ≦ Di ≦ 2) が空白を区切りとして書かれている.Ai は家 i の位置を表す偶数である.すべての i (1 ≦ i ≦ N - 1) について,Ai < Ai+1 を満たす.Di は命令が出された後に国民 i が歩き始める方向を表す.Di = 1 のときは国民 i は東向きに歩き始める.Di = 2 のときは国民 i は西向きに歩き始める.

続く Q 行のうち i 行目には,整数 Xi (1 ≦ Xi ≦ N) が書かれている.これは,i 番目の重要人物が家 Xi に住んでいることを表す.すべての i (1 ≦ i ≦ Q - 1) について,Xi < Xi+1 を満たす.

与えられる 5 つの入力データのうち,入力 1 では N ≦ 100,T ≦ 10000を満たす.また,入力 2 では N ≦ 5000 を満たす.また,入力 3 では,ある整数 M (1 ≦ M ≦ N - 1) があって,すべての i (1 ≦ i ≦ M) について Di = 1,すべての j (M + 1 ≦ j ≦ N) について Dj = 2 を満たす.また,入力 1,2,3 では,入力に与えられる整数の絶対値は 1000000000 (= 109) を超えない.入力 4,5 では,与えられる整数が 32 ビット符号付き整数の範囲に収まらないことに注意せよ.

出力

出力は Q 行からなる.

i 行目 (1 ≦ i ≦ 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

Source: 15th Japanese Olympiad in Informatics , 2015-12-13
http://www.ioi-jp.org/