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\) でない偶数 \(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\) 番目の重要人物の位置を表す整数を出力せよ．この値が整数であることは，問題文の条件より保証されている．

JOI 2016 · JCIOI · CC BY-SA 4.0