D - JOI国のお散歩事情 (Walking in JOI Kingdom) Editorial /

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\,0001 \leqq Q \leqq N) が空白を区切りとして書かれている.これは,JOI 国に家が N 軒あり,王様が命令を出してから T 秒後の,Q 人の重要人物の位置を把握しておきたいことを表す.

続く N 行のうち i 行目には,2 つの整数 A_i, D_i (-10^{18} \leqq A_i \leqq 10^{18}A_i0 でない偶数,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 100T \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