Problem: problem

The JOI country has one long enough road running east to west. The royal palace of JOI country is along the road, and the position along the road in JOI country is represented by the integer A. When A = 0, it represents the position of the royal palace. When A> 0, it indicates the position A meters east of the royal palace. When A <0, it represents a position that is -A meters west of the royal palace.

There are N houses along the roads in JOI, and the houses are numbered from 1 to N in order from the west. There are N people in JOI country, and the people are numbered from 1 to N. The people i live in the house i. The position of house i is represented by a non-zero even Ai. A1, ..., AN are all different.

In JOI country, the lack of movement of the people has become a problem in recent years. The King of JOI, who was concerned about the health of the people, ordered all the people to take a walk. When the King gives an order, all the people start walking eastward or westward all at once. The direction in which each nation starts walking is determined by each nation. All people walk at a speed of 1 meter per second when walking.

All the people of JOI love to talk. If you meet other people during your walk, you will stop there and start small talk. The same is true if you meet a people who have already stopped. The people who have stopped once will not start walking again.

There are Q important people in JOI country. The King of JOI wants to know the position of Q important persons T seconds after the order is issued. Create a program to find the position of Q important persons T seconds after the command is issued.

input

The input consists of 1 + N + Q lines.

On the first line, three integers N, T, Q (1 ≤ N ≤ 100000 (= 105), 0 ≤ T ≤ 1018, 1 ≤ Q ≤ 1000, 1 ≤ Q ≤ N) are written separated by blanks. ing. This means that there are N houses in JOI country, and we want to know the position of Q important people T seconds after the king issues the order.

Two integers Ai and Di (-1018 ≤ Ai ≤ 1018, Ai is a non-zero even number, 1 ≤ Di ≤ 2) are written on the i-th line of the following N lines, separated by blanks. Ai is an even number representing the position of house i. For all i (1 ≤ i ≤ N-1), Ai <Ai + 1 is satisfied. Di indicates the direction in which the national i starts walking after the command is issued. When Di = 1, national i starts walking eastward. When Di = 2, national i starts walking westward.

The integer Xi (1 ≤ Xi ≤ N) is written on the i-th line of the following Q lines. This means that the i-th important person lives in the house Xi. For all i (1 ≤ i ≤ Q-1), Xi <Xi + 1 is satisfied.

Of the five input data given, input 1 satisfies N ≤ 100 and T ≤ 10000. In addition, input 2 satisfies N ≤ 5000. Also, at input 3, there is a certain integer M (1 ≤ M ≤ N-1), Di = 1 for all i (1 ≤ i ≤ M), and for all j (M + 1 ≤ j ≤ N). Satisfy Dj = 2. Also, for inputs 1, 2, and 3, the absolute value of the integer given to the input does not exceed 1000000000 (= 109). Note that for inputs 4 and 5, the given integer does not fall within the range of 32-bit signed integers.

output

The output consists of Q lines.

On line i (1 ≤ i ≤ Q), output an integer representing the position of the i-th important person T seconds after the King issued the command. It is guaranteed that this value is an integer from the condition of the problem statement.

Input / output example

Input example 1


5 5 3
-8 1
-4 2
-twenty two
4 2
10 1
1
3
Five


Output example 1


-6
-6
15


Input example 2


7 18 5
-100 1
-56 2
-34 1
-30 1
-22 1
-4 2
18 2
1
3
Four
Five
7


Output example 2


-82
-16
-13
-13
0


Creative Commons License

Information Olympics Japan Committee work "15th Japan Information Olympics JOI 2015/2016 Qualifying Competition Tasks"





Example

Input

5 5 3
-8 1
-4 2
-2 2
4 2
10 1
1
3
5


Output

-6
-6
15

Solution (in CPP):

Solution:
/*
JOI国のお散歩事情
<問題>
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 でない偶数 Ai で表される．A1, ..., AN は全て異なる．
JOI 国では，近年国民の運動不足が問題になっている．
国民の健康が気になった JOI 国の王様は，国民全員に散歩をする命令を出した．
王様が命令を出すと，全ての国民は一斉に東向きまたは西向きに歩き始める．
それぞれの国民がどちらの向きに歩き始めるかは，国民ごとに決まっている．
全ての国民は，歩くときは 1 秒あたり 1 メートルの速度で歩く．
JOI 国の国民は皆おしゃべりが大好きである．散歩の途中にほかの国民に出会うと，
その場所で立ち止まって世間話を始めてしまう．
すでに立ち止まっている国民に出会った場合も同様である．一度立ち止まった国民は，再び歩き出すことはない．
JOI 国には Q 人の重要人物がいる．JOI 国の王様は，命令が出されてから T 秒後の，
Q 人の重要人物の位置を把握しておきたい．
命令が出されてから T 秒後の，Q 人の重要人物の位置を求めるプログラムを作成せよ．
<入力>
入力は，1 + N + Q 行からなる．

1 行目には，3 つの整数 N，T，Q (1 ≦ N ≦ 100000 (= 105),0 ≦ T ≦ 10の18乗, 
1 ≦ Q ≦ 1000，1 ≦ Q ≦ N) が空白を区切りとして書かれている．
これは ，JOI 国に家が N 軒あり，王様が命令を出してから T 秒後の，
Q 人の重要人物の位置を把握しておきたいことを表す．
続く N 行のうち i 行目には，2 つの整数 Ai, Di (-1018 ≦ Ai ≦ 1018, Ai は 0 でない偶数, 
1 ≦ Di ≦ 2) が空白を区切りとして書かれている．
Ai は家 i の位置を表す偶数である．すべての i (1 ≦ i ≦ N - 1) について，Ai < Ai+1 を満たす．
Di は命令が出された後に国民 i が歩き始める方向を表す．Di = 1 のときは国民 i は東向きに歩き始める．
Di = 2 のときは国民 i は西向きに歩き始める．
続く Q 行のうち i 行目には，整数 Xi (1 ≦ Xi ≦ N) が書かれている．
これは，i 番目の重要人物が家 Xi に住んでいることを表す．
すべての i (1 ≦ i ≦ Q - 1) について，Xi < Xi+1 を満たす．
与えられる 5 つの入力データのうち，入力 1 では N ≦ 100，T ≦ 10000を満たす．
また，入力 2 では N ≦ 5000 を満たす．また，入力 3 では，
ある整数 M (1 ≦ M ≦ N - 1) があって，すべての i (1 ≦ i ≦ M) について Di = 1，
すべての j (M + 1 ≦ j ≦ N) について Dj = 2 を満たす．
また，入力 1，2，3 では，入力に与えられる整数の絶対値は 1000000000 (= 109) を超えない．
入力 4，5 では，与えられる整数が 32 ビット符号付き整数の範囲に収まらないことに注意せよ．
*/

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
//dat["立ち止まる位置"]
long long dat[100010];
//vec[]
long long vec[100010][2];
int main(void){
	int num,query,i,j,z,zb;
	long long t,tt,za;
	i=0;
	cin>>num>>t>>query;
	vec[0][0]=-3000000000000000000LL;
	vec[0][1]=1;
	for(;i<num;i++){
		cin>>za>>zb;
		vec[i+1][0]=za;
		vec[i+1][1]=zb;
	}
	vec[num+1][0]=3000000000000000000LL;
	vec[num+1][1]=2;
	i=0;
	for(;i<=num;i++)
	{
		if(vec[i][1]==1&&vec[i+1][1]==2)
		{
			tt=(vec[i][0]+vec[i+1][0])/2;
			j=i;
			for(;j>=0;j--){
				if(vec[j][1]==1){
					dat[j]=tt;
				}
				else{
					break;
				}
			}
			j=i+1;
			for(;j<num+2;j++){
				if(vec[j][1]==2)
				{
					dat[j]=tt;
				}
				else{
					break;
				}
			}
		}
	}
	i=0;
	for(;i<query;i++){
		cin>>z;
		if(vec[z][1]==1){
			cout<<(vec[z][0]+t<dat[z]?(vec[z][0]+t):(dat[z]))<<endl;
		}
		else{
			cout<<(vec[z][0]-t<dat[z]?(dat[z]):(vec[z][0]-t))<<endl;
		}
	}
	return 0;
}
/*
#include<queue>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
stack<long long> q1;
stack<long long> q2;
int N=0,Q=0,T=0,D=0;
long long A[100010],syugou[1e9];
int main(void){
		cin>>N>>T>Q;
		for(int i=0;i<N;i++){
			cin>>A[i]>>D[i];
			if(D==1){
				q1.push(A[i]);
			}
			else
			{
				q2.push(A[i]);
			}
			if(q1.empty()==0&&q2.empty()==0)
			{
				if(D[i]==1)
				{
					syugou[i]=q1.top();
					syugou[i-1]=q2.top();
					while
					{
						
					}
				}
			}
		}
		return 0;
}*/