问题

JOI 国有一条从东到西的很长的道路。JOI 国王宫位于道路旁边，JOI 国的道路位置用整数 $A$ 表示。当 $A = 0$ 时，表示王宫的位置。当 $A > 0$ 时，表示从王宫向东前进 $A$ 米的位置。当 $A < 0$ 时，表示从王宫向西前进 $\-A$ 米的位置。

JOI 国的道路旁有 $N$ 栋房子，房子按照从西到东的顺序依次编号为 $1$ 到 $N$。JOI 国有 $N$ 名公民，每个公民都有一个从 $1$ 到 $N$ 的编号。第 $i$ 栋房子住着第 $i$ 名公民。每栋房子的位置用非零偶数 $A_i$ 表示。$A_1, \ldots, A_N$ 均互不相同。

近年来，JOI 国的公民缺乏运动，这成为了一个问题。国王非常关心公民的健康，因此下令让所有公民进行散步。一旦国王发布命令，所有公民立即开始朝东或朝西走。每个公民的行走方向是固定的。所有公民行走速度为每秒 $1$ 米。

JOI 国的公民都喜欢聊天。当他们在散步途中遇到其他公民时，他们会停下来聊天。即使遇到已经停下来的公民，情况也是一样。一旦停下来，他们将不再行走。

JOI 国有 $Q$ 名重要人物。国王希望在发布命令后的 $T$ 秒内掌握这 $Q$ 名重要人物的位置。请编写一个程序，求解发布命令后的 $T$ 秒内这 $Q$ 名重要人物的位置。

输入

输入共有 $1 + N + Q$ 行。

第一行包含 $3$ 个整数 $N, T, Q$ ($1 \leq N \leq 100,000 (= 10^5)$，$0 \leq T \leq 10^{18}$，$1 \leq Q \leq 1,000$，$1 \leq Q \leq N$)，以空格分隔。它表示 JOI 国有 $N$ 栋房子，国王希望在发布命令后的 $T$ 秒内掌握这 $Q$ 名重要人物的位置。

接下来的 $N$ 行中，第 $i$ 行包含 $2$ 个整数 $A_i, D_i$ ($-10^{18} \leq A_i \leq 10^{18}$，$A_i$ 是非零偶数，$1 \leq D_i \leq 2$)，以空格分隔。$A_i$ 表示第 $i$ 栋房子的位置，它是一个非零偶数。对于所有 $i$ ($1 \leq i \leq N - 1$)，满足 $A_i < A_{i + 1}$。$D_i$ 表示命令发布后公民 $i$ 的行走方向。当 $D_i = 1$ 时，公民 $i$ 向东走；当 $D_i = 2$ 时，公民 $i$ 向西走。

接下来的 $Q$ 行中，第 $i$ 行包含一个整数 $X_i$ ($1 \leq X_i \leq N$)。它表示第 $i$ 名重要人物居住在第 $X_i$ 栋房子。对于所有 $i$ ($1 \leq i \leq Q - 1$)，满足 $X_i < X_{i + 1}$。

对于给定的 $5$ 组输入数据，输入 $1$ 满足 $N \leq 100$，$T \leq 10,000$。输入 $2$ 满足 $N \leq 5,000$。输入 $3$ 满足存在一个整数 $M$ ($1 \leq M \leq N - 1$)，对于所有 $i$ ($1 \leq i \leq M$)，有 $D_i = 1$，对于所有 $j$ ($M + 1 \leq j \leq N$)，有 $D_j = 2$。输入 $1, 2, 3$ 中给定的整数的绝对值不超过 $1,000,000,000 (= 10^9)$。请注意，输入 $4, 5$ 中给定的整数超出了 $32$ 位有符号整数的范围。

输出

输出共有 $Q$ 行。

第 $i$ 行 ($1 \leq i \leq 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