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<iostream>
#include<algorithm>
using namespace std;
class people{
public:
    long long int place;
    int dotti;
};
int main(){
    int n;
    long long int T;
    int Q;
    cin>>n>>T>>Q;
    people *house;
    house=new people[n+2];
    for(int i=1;i<=n;++i){
        cin>>house[i].place>>house[i].dotti;
    }
    long long int dummy;
    house[0].dotti=2;
    house[n+1].dotti=1;
    for(int i=1;i+1<=n;++i){
        if(house[i].dotti==1&&house[i+1].dotti==2){
            if(house[i+1].place-house[i].place<=T*2){
                dummy=(house[i+1].place+house[i].place)/2;
                house[i].place=dummy;
                house[i+1].place=dummy;
                house[i].dotti=3;
                house[i+1].dotti=3;
            }else{
                house[i].place+=T;
                house[i+1].place-=T;
                house[i].dotti=3;
                house[i+1].dotti=3;
            }
        }
    }
    for(int i=1;i<=n;++i){
        if(house[i].dotti==2){
            if(house[i-1].dotti==3){
                house[i].place=max(house[i].place-T,house[i-1].place);
                house[i].dotti=3;
            }else{
                house[i].place-=T;
            }
        }else if(house[i].dotti==1){
            if(house[i+1].dotti==3){
                house[i].place=min(house[i].place+T,house[i+1].place);
                house[i].dotti=3;
            }else{
                house[i].place+=T;
            }
        }
    }
    int doll;
    for(int i=0;i<Q;++i){
        cin>>doll;
        cout<<house[doll].place<<endl;
    }
    return 0;
}

C++: #include <stdio.h>
#include <algorithm>

long long int N, T, Q;
long long int A[112345], D[112345];
long long int X[1123];
long long int t[112345];

int main(void) {
	scanf("%lld%lld%lld", &N, &T, &Q);
	for (long long int i = 0; i < N; ++i) { scanf("%lld%lld", &A[i], &D[i]); }
	for (long long int i = 0; i < Q; ++i) { scanf("%lld", &X[i]); }

	for (long long int i = 0; i < N - 1; ++i) {
		if (D[i] == 1 && D[i + 1] == 2) {
			long long int t_mem = (A[i] + A[i + 1]) / 2;
			t[i] = t_mem;
			t[i + 1] = t_mem;
			for (long long int j = i - 1; j >= 0; --j) {
				if (D[j] == 1) {
					t[j] = t_mem;
				}
				else { break; }
			}
			for (long long int j = i + 1; j < N; ++j) {
				if (D[j] == 2) {
					t[j] = t_mem;
				}
				else { break; }
			}
		}
	}

	for (long long int i = 0; i < N; ++i) {
		if(T<std::abs(A[i]-t[i])){
			if (D[i] == 1) {
				t[i] = A[i] + T;
			}
			if (D[i] == 2) {
				t[i] = A[i] - T;
			}
		}
	}

	for (long long int i = 0; i < Q; ++i) {
		printf("%lld\n", t[X[i] - 1]);
	}

	return 0;
}

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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

#define MAX 100000
typedef long long ll;
typedef pair<int,int> ii;

struct Data {
  ll x,index, l_index;
  bool operator < ( const Data &data ) const {
    return x < data.x;
  }
};

int N, Q, sum[MAX+1];
ll T;
vector<Data> ps[2];
ii mp[MAX];

void compute() {
  if( ps[0].empty() || ps[1].empty() ) {
    int which = (ps[0].size()?0:1);
    rep(i,Q) {
      int tmp;
      cin >> tmp;
      --tmp;
      cout << ps[which][tmp].x + ( which ? -T : T ) << endl;
    }
    return;
  }
  rep(i,2) sort(ps[i].begin(),ps[i].end());
  vector<ll> collision_point;
  vector<ll> collision_time;
  rep(i,(int)ps[0].size()) {
    int p = lower_bound(ps[1].begin(),ps[1].end(),ps[0][i]) - ps[1].begin();
    if( p == (int)ps[1].size() ) continue;
    Data L = ps[0][i], R = ps[1][p];
    assert( L.x < R.x );
    int cnt = sum[R.l_index-1] - sum[L.l_index];
    if( cnt ) continue;
    collision_point.push_back( ( L.x + R.x ) / 2LL );
    collision_time.push_back( collision_point.back() - L.x );
  }
  rep(i,Q) {
    int tmp;
    cin >> tmp;
    --tmp;
    ii index = mp[tmp];
    Data &e = ps[index.first][index.second];
    ll ans = e.x + ( index.first ? -T : T );
    rep(j,(int)collision_point.size()) {
      if( collision_time[j] > T ) continue;
      if(  index.first && collision_point[j] > e.x ) continue;
      if( !index.first && collision_point[j] < e.x ) continue;
      ll tmp_p = e.x + ( index.first ? -1LL : 1LL ) * collision_time[j];
      bool collision = false;
      if(  index.first && collision_point[j] <= tmp_p ) collision = true;
      if( !index.first && collision_point[j] >= tmp_p ) collision = true;
      if( !collision ) continue;
      ll c_diff = llabs(ans-e.x);
      ll n_diff = llabs(collision_point[j]-e.x);
      if( c_diff > n_diff ) ans = collision_point[j];
    }
    cout << ans << endl;
  }
}

int main() {
  cin >> N >> T >> Q;
  vector<ll> vec;
  rep(i,N) {
    ll a,b;
    cin >> a >> b;
    mp[i] = ii(b-1,(int)ps[b-1].size());
    ps[b-1].push_back((Data){a,i,-1});
    vec.push_back(a);
  }
  sort(vec.begin(),vec.end());
  rep(i,2) rep(j,(int)ps[i].size()) {
    ps[i][j].l_index = lower_bound(vec.begin(),vec.end(),ps[i][j].x) - vec.begin();
  }
  rep(i,2) rep(j,(int)ps[i].size()) {
    ++sum[ps[i][j].l_index];
  }
  REP(i,1,(int)vec.size()+1) sum[i] += sum[i-1];
  compute();
  return 0;
}