JOI 王国有一条沿东西方向延伸、足够长的 $1$ 条道路。JOI 王国的王宫位于道路旁，JOI 王国中道路旁的位置用整数 $A$ 表示。当 $A = 0$ 时表示王宫的位置。当 $A > 0$ 时表示从王宫向东前进 $A$ 米的位置。当 $A < 0$ 时表示从王宫向西前进 $-A$ 米的位置。

JOI 王国的道路旁有 $N$ 栋房子，房子按从西到东的顺序从 $1$ 到 $N$ 编号。JOI 王国有 $N$ 名国民，国民从 $1$ 到 $N$ 编号。房子 $i$ 里住着国民 $i$。房子 $i$ 的位置用非零偶数 $A_i$ 表示。$A_1, \dots, A_N$ 互不相同。

在 JOI 王国，近年来国民缺乏运动成为了一个问题。关心国民健康的 JOI 王国国王向全体国民下达了散步的命令。国王下达命令后，所有国民同时开始向东或向西行走。每名国民开始向哪个方向行走是由每名国民各自决定的。所有国民在行走时均以每 $1$ 秒 $1$ 米的速度行走。

JOI 王国的国民都非常喜欢聊天。如果在散步途中遇到其他国民，就会在那个地方停下脚步开始闲聊。遇到已经停下脚步的国民时也是如此。一旦停下脚步的国民，就不会再次开始行走。

JOI 王国有 $Q$ 名重要人物。JOI 王国的国王希望掌握命令下达 $T$ 秒后这 $Q$ 名重要人物的位置。请编写程序，求出命令下达 $T$ 秒后这 $Q$ 名重要人物的位置。

输入格式

输入由 $1 + N + Q$ 行组成。

第 $1$ 行写有 $3$ 个以空格分隔的整数 $N, T, Q$（$1 \le N \le 100000 (= 10^5), 0 \le T \le 10^{18}, 1 \le Q \le 1000, 1 \le Q \le N$）。这表示 JOI 王国有 $N$ 栋房子，国王希望掌握命令下达 $T$ 秒后 $Q$ 名重要人物的位置。

接下来 $N$ 行中的第 $i$ 行写有 $2$ 个以空格分隔的整数 $A_i, D_i$（$-10^{18} \le A_i \le 10^{18}$，$A_i$ 为非零偶数，$1 \le D_i \le 2$）。$A_i$ 是表示房子 $i$ 位置的偶数。对于所有 $i$（$1 \le i \le N - 1$），满足 $A_i < A_{i+1}$。$D_i$ 表示命令下达后国民 $i$ 开始行走的方向。当 $D_i = 1$ 时，国民 $i$ 开始向东行走。当 $D_i = 2$ 时，国民 $i$ 开始向西行走。

接下来 $Q$ 行中的第 $i$ 行写有整数 $X_i$（$1 \le X_i \le N$）。这表示第 $i$ 名重要人物住在房子 $X_i$ 中。对于所有 $i$（$1 \le i \le Q - 1$），满足 $X_i < X_{i+1}$。

在给定的 $5$ 组输入数据中，输入 $1$ 满足 $N \le 100, T \le 10000$。输入 $2$ 满足 $N \le 5000$。输入 $3$ 满足存在某个整数 $M$（$1 \le M \le N - 1$），使得对于所有 $i$（$1 \le i \le M$）满足 $D_i = 1$，且对于所有 $j$（$M + 1 \le j \le N$）满足 $D_j = 2$。此外，在输入 $1, 2, 3$ 中，输入给定的整数的绝对值不超过 $1000000000 (= 10^9)$。请注意，在输入 $4, 5$ 中，给定的整数可能超出 $32$ 位有符号整数的范围。

输出格式

输出由 $Q$ 行组成。

在第 $i$ 行（$1 \le i \le 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