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:
#include <bits/stdc++.h>
                                        #include<iostream>
                                        #include<cstdio>
                                        #include<vector>
                                        #include<queue>
                                        #include<map>
                                        #include<cstring>
                                        #include<string>
                                        #include <math.h>
                                        #include<algorithm>
                                    //    #include <boost/multiprecision/cpp_int.hpp>
                                        #include<functional>
                               #define int long long
                                        #define inf  1000000007
                                        #define pa pair<int,int>
                                        #define ll long long
                                        #define pal pair<double,double>
                                        #define ppap pair<pa,int>
                                  
                                        #define ssa pair<string,int>
                                        #define  mp make_pair
                                        #define  pb push_back
                                        #define EPS (1e-7)
                                        #define equals(a,b) (fabs((a)-(b))<EPS)
int dx[4]={0,-1,0,1};
int dy[4]={1,0,-1,0};
                                        using namespace std;
                               			class pa3{
                                        	public:
                                        	int x,y,z;
                                        	pa3(int x=0,int y=0,int z=0):x(x),y(y),z(z) {}
                                        	bool operator < (const pa3 &p) const{
                                        		if(x!=p.x) return x<p.x;
                                        		if(y!=p.y) return y<p.y;
                                        		 return z<p.z;
                                        		//return x != p.x ? x<p.x: y<p.y;
                                        	}
                               				bool operator > (const pa3 &p) const{
                                        		if(x!=p.x) return x>p.x;
                                        		if(y!=p.y) return y>p.y;
                                        		 return z>p.z;
                                        		//return x != p.x ? x<p.x: y<p.y;
                                        	}
                                        	bool operator == (const pa3 &p) const{
                                        		return x==p.x && y==p.y && z==p.z;
                                        	}
                                        		bool operator != (const pa3 &p) const{
                                        			return !( x==p.x && y==p.y && z==p.z);
                                        	}
                                        
                                        };
                                        
                                        class pa4{
                                        	public:
                                        	int x;
                                        	int y,z,w;
                                        	pa4(int x=0,int y=0,int z=0,int w=0):x(x),y(y),z(z),w(w) {}
                                        	bool operator < (const pa4 &p) const{
                                        		if(x!=p.x) return x<p.x;
                                        		if(y!=p.y) return y<p.y;
                                        		if(z!=p.z)return z<p.z;
                                        		return w<p.w;
                                        		//return x != p.x ? x<p.x: y<p.y;
                                        	}
                                        	bool operator > (const pa4 &p) const{
                                        		if(x!=p.x) return x>p.x;
                                        		if(y!=p.y) return y>p.y;
                                        		if(z!=p.z)return z>p.z;
                                        		return w>p.w;
                                        		//return x != p.x ? x<p.x: y<p.y;
                                        	}
                                        	bool operator == (const pa4 &p) const{
                                        		return x==p.x && y==p.y && z==p.z &&w==p.w;
                                        	}
                                        		
                                        
                                        };
                                        class pa2{
                                        	public:
                                        	int x,y;
                                        	pa2(int x=0,int y=0):x(x),y(y) {}
                                        	pa2 operator + (pa2 p) {return pa2(x+p.x,y+p.y);}
                                        	pa2 operator - (pa2 p) {return pa2(x-p.x,y-p.y);}
                                        	bool operator < (const pa2 &p) const{
                                        		return x != p.x ? x<p.x: y<p.y;
                                        	}
                                        	bool operator > (const pa2 &p) const{
                                        		return x != p.x ? x>p.x: y>p.y;
                                        	}
                                        	bool operator == (const pa2 &p) const{
                                        		return abs(x-p.x)==0 && abs(y-p.y)==0;
                                        	}
                                        	bool operator != (const pa2 &p) const{
                                        		return !(abs(x-p.x)==0 && abs(y-p.y)==0);
                                        	}
                                        		
                                        
                                        };
                                        
                                               #define ppa pair<int,pas>
                                        class Point{
                                        	public:
                                        	double x,y;
                                        	Point(double x=0,double y=0):x(x),y(y) {}
                                        	Point operator + (Point p) {return Point(x+p.x,y+p.y);}
                                        	Point operator - (Point p) {return Point(x-p.x,y-p.y);}
                                        	Point operator * (double a) {return Point(x*a,y*a);}
                                        	Point operator / (double a) {return Point(x/a,y/a);}
                                        	double absv() {return sqrt(norm());}
                                        	double norm() {return x*x+y*y;}
                                        	bool operator < (const Point &p) const{
                                        		return x != p.x ? x<p.x: y<p.y;
                                        	}
                                        	bool operator == (const Point &p) const{
                                        		return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
                                        	}
                                        };
                                        typedef Point Vector;
                                 #define pl pair<int,pas>
                                        struct Segment{
                                        Point p1,p2;
                                        };
                                         double dot(Vector a,Vector b){
                                        	return a.x*b.x+a.y*b.y;
                                        }
                                        double cross(Vector a,Vector b){
                                        	return a.x*b.y-a.y*b.x;
                                        }
                                    
            bool parareru(Point a,Point b,Point c,Point d){
            //	if(abs(cross(a-b,d-c))<EPS)cout<<"dd "<<cross(a-b,d-c)<<endl;
            	return abs(cross(a-b,d-c))<EPS;
            }
            double distance_ls_p(Point a, Point b, Point c) {
              if ( dot(b-a, c-a) < EPS ) return (c-a).absv();
              if ( dot(a-b, c-b) < EPS ) return (c-b).absv();
              return abs(cross(b-a, c-a)) / (b-a).absv();
            }
            bool is_intersected_ls(Segment a,Segment b) {
            	if(a.p1==b.p1||a.p2==b.p1||a.p1==b.p2||a.p2==b.p2) return false;
            	if(parareru((a.p2),(a.p1),(a.p1),(b.p2))&&parareru((a.p2),(a.p1),(a.p1),(b.p1))){
            //		cout<<"sss"<<endl;
            		if(dot(a.p1-b.p1,a.p1-b.p2)<EPS) return true;
            		if(dot(a.p2-b.p1,a.p2-b.p2)<EPS) return true;
            		if(dot(a.p1-b.p1,a.p2-b.p1)<EPS) return true;
            		if(dot(a.p1-b.p2,a.p2-b.p2)<EPS) return true;
            		return false;
            	}
              else return ( cross(a.p2-a.p1, b.p1-a.p1) * cross(a.p2-a.p1, b.p2-a.p1) < EPS ) && ( cross(b.p2-b.p1, a.p1-b.p1) * cross(b.p2-b.p1, a.p2-b.p1) < EPS );
            }
             
            double segment_dis(Segment a,Segment b){
            	if(is_intersected_ls(a,b))return 0;
            	double r=distance_ls_p(a.p1, a.p2, b.p1);
            	r=min(r,distance_ls_p(a.p1, a.p2, b.p2));
            	r=min(r,distance_ls_p(b.p1, b.p2, a.p2));
            	r=min(r,distance_ls_p(b.p1, b.p2, a.p1));
            	return r;
            }
            Point intersection_ls(Segment a, Segment b) {
              Point ba = b.p2-b.p1;
              double d1 = abs(cross(ba, a.p1-b.p1));
              double d2 = abs(cross(ba, a.p2-b.p1));
              double t = d1 / (d1 + d2);
             
              return a.p1 + (a.p2-a.p1) * t;
            }
             
                            string itos( int i ) {
                            ostringstream s ;
                            s << i ;
                            return s.str() ;
                            }
                             
                            int gcd(int v,int b){
                            	if(v>b) return gcd(b,v);
                            	if(v==b) return b;
                            	if(b%v==0) return v;
                            	return gcd(v,b%v);
                            }
             
                            double distans(double x1,double y1,double x2,double y2){
                            	double rr=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
                            	return sqrt(rr);
                            	
                            }
                            
   //         int pr[2000010];
     //       int inv[2000010];
            
            int beki(int wa,int rr,int warukazu){
            	if(rr==0) return 1ll;
            	if(rr==1) return wa%warukazu;
            	if(rr%2==1) return (beki(wa,rr-1,warukazu)*wa)%warukazu;
            	int zx=beki(wa,rr/2,warukazu);
            	return (zx*zx)%warukazu;
            }
            /*
			int comb(int nn,int rr){
				int r=pr[nn]*inv[rr];
				r%=inf;
				r*=inv[nn-rr];
				r%=inf;
				return r;
			}
            
            void gya(int ert){
            	pr[0]=1;
            	for(int i=1;i<ert;i++){
            		pr[i]=(pr[i-1]*i)%inf;
            	}
            	for(int i=0;i<ert;i++) inv[i]=beki(pr[i],inf-2,inf);
            	
            }
             */
			//priority_queue<pa3,vector<pa3>,greater<pa3>> pq;            
             //sort(ve.begin(),ve.end(),greater<int>());
                                     //----------------kokomade tenpure------------
unsigned int randxor()
{
    static unsigned int x=123456789,y=362436069,z=521288629,w=88675123;
    unsigned int t;
    t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}
int a[100020],d[100020],pos[100020];
bool ch[100020]={0},sumi[100020]={0};
  signed main(){
  	              cin.tie(0);
    		ios::sync_with_stdio(false);
int n,t,q;
  	cin>>n>>t>>q;
  	for(int i=1;i<=n;i++)cin>>a[i]>>d[i];
  	for(int i=1;i<=n;i++){
  		if(d[i]==1)break;
  		ch[i]=1;
  		sumi[i]=1;
  	}
  	for(int i=n;i>0;i--){
  		if(d[i]==2) break;
  		ch[i]=1;
  		sumi[i]=1;
  	}
  	
  	for(int i=1;i<n;i++)if(d[i]==1 && d[i+1]==2){
  		pos[i]=(a[i]+a[i+1])/2;
  		pos[i+1]=pos[i];
  		sumi[i]=1;
  		sumi[i+1]=1;
  	}
  	
  	for(int i=1;i<=n;i++)if(!ch[i])if(!sumi[i])if(d[i]==2)pos[i]=pos[i-1];
  	for(int i=n;i>0;i--)if(!ch[i])if(!sumi[i])if(d[i]==1)pos[i]=pos[i+1];
  	
  	for(int i=0;i<q;i++){
  		int y;
  		cin>>y;
  		
  		if(ch[y]){
  			if(d[y]==2) cout<<a[y]-t<<endl;
  			else cout<<a[y]+t<<endl;
  		}
  		else{
  			if(d[y]==2) cout<<max(a[y]-t,pos[y])<<endl;
  			else cout<<min(a[y]+t,pos[y])<<endl;
  		}
  	}
  	
  	return 0;
                }