题目描述

JOI 国有一条足够长的东西走向的道路。视该道路为一条数轴，则王宫在原点（表示数 $0$ 的点）的位置上。道路沿线的位置上的数可以用 $a$ 来表示，如果 $a>0$ ，则该地点在王宫的东边，距王宫 $a$ 米远；如果 $a<0$ ，则该地点在王宫的西边，距王宫 $-a$ 米远。

这条道路的沿线有 $n$ 户人家，编号从西到东依次为 $1$ 到 $n$ 。记编号为 $i$ 的人家的位置为 $a_i$ ，则对于所有满足 $0<i<n$ 的整数 $i$ 来说， $a_i$ 永远比 $a_{i+1}$ 小。对于满足 $1≤i≤n$ 的所有整数 $i$ ，数据保证 $a_i≠0$ 且 $a_i$ 必为偶数。

近年来，在 JOI 国，国民运动不足已成为一大问题。在意国民健康的国王今天下令：“所有国民同时开始散步！”命令发出后，每位国民都会开始向正西或正东方向移动。

然而 JOI 国的国民相互之间已经非常熟悉。每当遇到其他国民时，他们都会停下来聊天。如果路过的其它国民看到有人在聊天，他也会停下来并加入进去。停下来聊天的国民再也不会开始走路。

JOI 国有 $q$ 为重要人物，第 $i$ 位重要人物住在编号为 $x_i$ 的人家。则对于所有满足 $0<i<q$ 的整数 $i$ 来说， $x_i$ 永远比 $x_{i+1}$ 小。

现在国王想了解这 $q$ 位人物 $t$ 秒后到了什么位置。请你帮国王编写程序，解决他的问题。

输入格式

输入 $(n+q+1)$ 行。

第一行：三个非负整数 $n,t,q$ ，相邻的两个正整数之间以单个空格隔开。

第二行到第 $(n+1)$ 行：每行两个整数，中间以单个空格隔开。第 $(i+1)$ 行的两个整数为 $a_i$ 和 $d_i$ ，其中 $a_i$ 为第 $i$ 户人家的位置， $d_i$ 为 $1$ 时表示国王下令后这户人家的人会往东走，为 $2$ 时表示国王下令后这户人家的人会往西走。

第 $(n+2)$ 行到第 $(n+q+1)$ 行：每行一个正整数。第 $(n+i+1)$ 行的整数为 $x_i$ ，表示询问第 $i$ 位人物在开始散步 $t$ 秒后的位置。

输出格式

输出 $q$ 行，每行一个整数，第 $i$ 行的整数表示第 $i$ 位重要人物的当前位置。

提示

对于全部的输入数据，保证：

• $1≤q≤n≤10^5$ ；
• $1≤t≤10^{18}$ ；
• $-10^{18}≤a_i≤10^{18}$ ，$0<d_i<3$ ；
• $1≤x_i≤n$ ；
• 所有输入都是整数。