题目描述

一条道路上，位置点用整数 $A$ 表示。

当 $A=0$ 时，有一个王宫。当 $A>0$，就是离王宫的东边有 $A$ 米，当 $A<0$，就是离王宫的西边有 $-A$ 米。

道路上，有 $N$ 个住宅从西向东用 $1\sim N$ 来标号。每个住宅有一个人。住宅只会存在于偶数整数点。

该国国王认为，国民体质下降，必须要多运动，于是下命令所有人都必须出门散步。所有的国民，一秒钟可以走 $1$ 米。每个国民各自向东或者向西走。这些方向你是知道的。命令发出后所有人同时离开家门开始散步。

然而该国的国民个都很健谈，如果在散步途中两个人相遇，就会停下来交谈。正在走路的人碰到已经停下来的人（重合）也会停下来交谈。一但停下来，就会聊到天昏地暗，忘记了散步。

现在命令已经发出了 $T$ 秒，该国有 $Q$ 个重要人物，国王希望能够把握他们的位置。你能帮他解答吗？

输入格式

第一行是 $3$ 个整数，$N,T,Q$

接下来 $N$ 行，每行两个整数 $A_i,R_i$。$A_i$ 是家的坐标，如果 $R_i$ 是 $1$，那么会向东走，如果是 $2$，向西。数据保证 $A_i$ 是升序排序，而且不会有两个人初始位置重合。

接下来 $Q$ 行，每行一个整数，表示国王关心的重要人物。

输出格式

$Q$ 行，每行一个整数，表示这个人的坐标。

6 6 4
-10 1
-6 2
-4 1
2 1
6 2
18 2
2
3
4
6

-8
2
4
12

提示

$20\%$ 数据，$N\le 100,T\le 10000$。

另外 $20\%$ 数据，$N\le 5000$。

另外 $20\%$ 数据，从最西边数起连续的若干国民全部往东，剩下的全部往西。

$100\%$ 数据 $A_i$ 为偶数，$|A_i|\le 10^{18},|T|\le 10^{18},1\le Q\le N\le 100000$。