Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {

	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	args := strings.Split(sc.Text(), " ")
	n, _ := strconv.Atoi(args[0])
	t, _ := strconv.ParseInt(args[1], 10, 64)

	q, _ := strconv.Atoi(args[2])

	pos := make([]int64, n)
	direction := make([]bool, n)

	for i := 0; i < n; i++ {
		sc.Scan()
		args = strings.Split(sc.Text(), " ")

		pos[i], _ = strconv.ParseInt(args[0], 10, 64)
		q, _ := strconv.Atoi(args[1])
		if q == 1 {
			direction[i] = true
		}
	}

	qq := make([]int, q)
	for i := 0; i < q; i++ {
		sc.Scan()
		args = strings.Split(sc.Text(), " ")

		qq[i], _ = strconv.Atoi(args[0])
	}

	ans(n, q, t, pos, direction, qq)

}

func ans(n, q int, t int64, pos []int64, dir []bool, qq []int) {

	colleation := []int64{} // syoutotu positon

	for i := 1; i < n; i++ {
		if dir[i-1] == dir[i] {
			continue
		}
		colleation = append(colleation, (pos[i-1]+pos[i])/2)

	}
	//fmt.Println(colleation)
	for i := 0; i < q; i++ {
		var ans int64
		ans = int64(-9999999)
		if dir[qq[i]-1] == true {
			// 東向きなら現ポジから＋方向で一番近い衝突点との距離を求めて、Tとの差が
			for _, v := range colleation {
				if v <= pos[qq[i]-1] {
					continue
				} else {
					// 衝突予定点が確定。衝突点との距離がT以下なら衝突点で停止
					if v-pos[qq[i]-1] <= t {
						ans = v
					} else {
						ans = pos[qq[i]-1] + int64(t)
					}
					break
				}
			}
			if ans == -9999999 {
				ans = pos[qq[i]-1] + int64((t))
			}

		} else {
			// nishi向きなら現ポジから-方向で一番近い衝突点との距離を求めて、Tとの差が
			for j := len(colleation); j > 0; j-- {
				if colleation[j-1] >= pos[qq[i]-1] {
					continue
				}
				v := colleation[j-1]
				//fmt.Printf("hoge=%d\n", v)
				// 衝突予定点が確定
				if pos[qq[i]-1]-v <= t {
					ans = v
				} else {
					ans = pos[qq[i]-1] - int64((t))
				}
				break

			}
			if ans == -9999999 {
				ans = pos[qq[i]-1] - int64((t))
			}

		}
		fmt.Printf("%d\n", ans)

	}

}

C++: #include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
P p[100010];
vector <ll>x;


int search(ll X){
  int L=0,M,R=x.size();
  while(L<R){
    M=(L+R)/2;
    if(X<=x[M]) R=M;
    else L=M+1;
  }
  return L;
}

int main(){
  ll n,T,q;
  cin>>n>>T>>q;

  int pre;
  for(int i=0,dir;i<n;i++){
    ll a;
    cin>>a>>dir;
    dir--;
    p[i]=P(a,dir);
    if(i&&pre!=dir){
      ll dis=(p[i].f+p[i-1].f)/2;
      if(dis<=2*T)x.push_back(dis);
    }
    pre=dir;
  }

  //  for(int i=0;i<x.size();i++)cout <<x[i]<<" ";cout <<endl;

  while(q--){
    int Q;
    cin>>Q;
    Q--;
    ll a=p[Q].f;
    int dir=p[Q].s;
    int idx=search(a)-(dir? 1:0);
    ll ans=(dir? -1:1)*T+a;
    if(!((dir==1&&idx==-1)||(dir==0&&idx==(int)x.size()))&&abs(x[idx]-a)<=T)ans=x[idx];
    cout <<ans<<endl;
  }
  return 0;
}

C++: #include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;
int d[100001];
long long k[100001],a[100001];
int main(void)
{
	int n,q,i,cnt,x,j,flg;
	long long MAX,MAX2,t,aa;
	scanf("%d %lld %d",&n,&t,&q);
	cnt=0;
	flg=0;
	for(i=1;i<=n;i++){
		scanf("%lld %d",&a[i],&d[i]);
		if(d[i]==1){
			MAX=a[i];
			flg=1;
		}
		if(flg==1&&d[i]==2&&(a[i]-MAX)/2<t){
			k[cnt]=(long long)(MAX+a[i])/2;
			flg=0;
			cnt++;
		}
	}
	for(i=0;i<q;i++){
		scanf("%d",&x);
		if(d[x]==1){
				aa=a[x]+t;
			}
		if(d[x]==2){
			aa=a[x]-t;
		}
		for(j=0;j<cnt;j++){
			if(aa>k[j]&&d[x]==1&&a[x]<k[j]){
				aa=k[j];
			}
			if(aa<k[j]&&d[x]==2&&a[x]>k[j]){
				aa=k[j];
			}
		}
		printf("%lld\n",aa);
	}	
	return 0;
}

C++: #include <bits/stdc++.h>

#define whole(xs) xs.begin(),xs.end()

using namespace std;

namespace {

    typedef double real;
    typedef long long ll;

    const ll INF = 1LL<<56;

    template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) {
        if (vs.empty()) return os << "[]";
        os << "[" << vs[0];
        for (int i = 1; i < vs.size(); i++) os << " " << vs[i];
        return os << "]";
    }
    template<class T> istream& operator>>(istream& is, vector<T>& vs) {
        for (auto it = vs.begin(); it != vs.end(); it++) is >> *it;
        return is;
    }

    struct P {
        int index;
        int a, d;
        P() {}
        P(int index, int a, int d) : index(index), a(a), d(d) {}
    };
    bool operator<(const P& a, const P& b) {
        return a.a < b.a;
    }

    ll N, T, Q;
    vector<P> X;
    vector<int> I;
    void input() {
        cin >> N >> T >> Q;
        X.clear(); X.resize(N);
        for (int i = 0; i < N; i++) {
            X[i].index = i;
            cin >> X[i].a >> X[i].d;
        }
        I.clear(); I.resize(Q);
        for (int i = 0; i < N; i++) {
            int q; cin >> q; q--;
            I[i] = q;
        }
    }


    void solve() {
        sort(whole(X));
        vector<ll> stop(N);
        vector<P> es;
        for (int i = 0; i < N; i++) {
            const P& a = X[i];
            if (a.d == 1) {
                es.push_back(a);
            } else {
                if (es.empty()) {
                    stop[a.index] = -INF;
                } else {
                    ll s = (es.back().a + a.a) / 2;
                    stop[a.index] = s;
                    for (const auto& e : es) {
                        stop[e.index] = s;
                    }
                    es.clear();
                }
            }
        }
        for (auto e : es) {
            stop[e.index] = INF;
        }

        for (int q = 0; q < Q; q++) {
            int i = I[q];
            if (X[i].d == 1) {
                cout << min(stop[i], X[i].a + T) << endl;
            } else {
                cout << max(stop[i], X[i].a - T) << endl;
            }
        }

    }
}

int main() {
    input(); solve();
    return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;

using LL = long long;

int main() {
  int N, T, Q;
  cin >> N >> T >> Q;

  vector<LL> A(N), D(N);
  set<LL> s[2];
  for(auto i = 0; i < N; ++i) {
    cin >> A[i] >> D[i];
    s[--D[i]].emplace(A[i]);
  }
  s[0].emplace(-2e18);
  s[1].emplace(2e18);

  for(auto q = 0; q < Q; ++q) {
    int X;
    cin >> X;
    if(D[--X]) {
      auto x = *--s[0].upper_bound(A[X]);
      auto y = *s[1].upper_bound(x);
      cout << max(A[X]-T, x+(y-x)/2) << endl;
    } else {
      auto x = *s[1].upper_bound(A[X]);
      auto y = *--s[0].upper_bound(x);
      cout << min(A[X]+T, x-(x-y)/2) << endl;
    }
  }
}

C++: #include <bits/stdc++.h>
using namespace std;
const int dx[]={1,0,-1,0,1,-1,-1,1};
const int dy[]={0,1,0,-1,1,1,-1,-1};
const int INF = 1e9;
const long long LINF = 1e18;
const double EPS = 1e-8;
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define ll long long
#define reps(i,j,k) for(int i = (j); i < (k); ++i)
#define rep(i,j) reps(i,0,j)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
typedef pair<int,int> Pii;
typedef vector<int> vi;
typedef pair<string, int> Psi;
typedef pair<ll, ll> Pll;

ll A[100001];
int way[100001];

vector<ll> points;

ll search(int idx,ll T){
	ll l = 0;
	ll r = points.size();
	while(l + 1 != r){
		int med = (l+r)/2;
		if(points[med] > A[idx]){
			r = med;
		}
		else{
			l = med;
		}
	}

	int s;
	ll c;
	if(way[idx] == 1){
		s = l + 1;
		c = 1;
	}
	else if(way[idx] == 2){
		s = l;
		c = -1;
	}
	if(T >= abs(A[idx]-points[s])){
		return points[s];
	}
	return A[idx]+c*T;
}

int main(){
	int N,Q;
	ll T;
	scanf("%d%lld%d",&N,&T,&Q);
	points.PB(-LINF);
	rep(i,N){
		scanf("%lld%d",&A[i],&way[i]);
		if(i > 0 && way[i-1] == 1 && way[i] == 2){
			points.PB(A[i-1]+(A[i]-A[i-1])/2);
		}
	}

	points.PB(LINF);
	rep(i,Q){
		int x;
		scanf("%d",&x);
		--x;
		printf("%lld\n",search(x,T));
	}

	return 0;
}