配点: 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