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 <cstdio>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;

int n, t, q;
long long int a[100000];
int d[100000];
int x[100000];

vector<long long int> v;
const long long int INF = 3e18;

int main(){
	scanf("%d %d %d", &n, &t, &q);
	for(int i=0; i<n; i++) scanf("%lld %d", &a[i], &d[i]);
	for(int i=0; i<q; i++) scanf("%d", &x[i]);

	v.push_back(-INF);
	bool f = false;
	long long int p;
	for(int i=0; i<n; i++){
		if(d[i] == 1){
			p = a[i];
			f = true;
		}else if(f){
			v.push_back(p / 2 + a[i] / 2);
			f = false;
		}
	}
	v.push_back(INF);

	long long int s;
	for(int i=0; i<q; i++){
		if(d[x[i]-1] == 1){
			s = *upper_bound(v.begin(), v.end(), a[x[i]-1]);
			if(s - a[x[i]-1] < t) printf("%lld\n", s);
			else printf("%lld\n", a[x[i]-1] + t);
		}else{
			s = *(lower_bound(v.begin(), v.end(), a[x[i]-1])-1);
			if(a[x[i]-1] - s < t) printf("%lld\n", s);
			else printf("%lld\n", a[x[i]-1] - t);
		}
	}
/*
	printf("\n");
	for(int i=0; i<v.size(); i++)
		printf("%lld\n", v[i]);
*/	return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#define int long long
const int INF=1e18;
using namespace std;
signed main(){
  int n,t,q,x[100000],y[100000],z[100000];
  vector <int> x0;
  cin>>n>>t>>q;
  for(int i=0;i<n;i++) cin>>x[i]>>y[i];
  for(int i=0;i<n-1;i++) if(y[i]==1&&y[i+1]==2) x0.push_back((x[i]+x[i+1])/2);
  int ch=-INF,a=-1;
  for(int i=0;i<n;i++) if(y[i]==2){
      if(x0[a+1]<x[i]){
        ch=x0[a+1];
        a++;
      }
      z[i]=ch;
      if(x[i]-z[i]>t) z[i]=x[i]-t;
    }
  //reverse(x0.begin(),x0.end());                                                                                              
  ch=INF,a=x0.size();
  for(int i=n-1;i!=-1;i--) if(y[i]==1){
      if(x0[a-1]>x[i]){
        ch=x0[a-1];
        a--;
      }
      z[i]=ch;
      if(z[i]-x[i]>t) z[i]=x[i]+t;
    }
  for(int i=0,d;i<q&&cin>>d;i++) cout<<z[d-1]<<endl;
}

C++: #include<stdio.h>


int main() {
	int N, T, Q;
	int A[10000], D[10000], X[10000];
	scanf("%d %d %d", &N, &T, &Q);
	for (int i = 1; i <= N; i++) {
		scanf("%d %d", &A[i], &D[i]);
		if (D[i] == 2) D[i] = -1;
	}
	for (int i = 1; i <= Q; i++) {
		scanf("%d", &X[i]);
	}
	for (int i = 1; i <= T; i++) {
		if (D[i] != 0) {
			for (int j = 1; j <= N; j++) {
				A[j] += D[j];
				if (A[j] == A[j - 1]) {
					D[j] = 0;
					D[j - 1] = 0;
				}
				if (A[j] == A[j + 1]) {
					D[j] = 0;
					D[j + 1] = 0;
				}
			}
		}
	}
	for (int i = 1; i <= Q; i++) {
		printf("%d\n", A[X[i]]);
	}
	
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
typedef struct{
  long long first,second;
  long long place;
}PA;
vector<PA> vec;

void east(int n,long long place){
  if(vec[n].second == 1){
    vec[n].place = place;
    east(n-1,place);
  }
}

void west(int n,long long place){
  if(vec[n].second == 2){
    vec[n].place = place;
    west(n+1,place);
  }
}

int main(){
  int n,q,b,c;
  long long t,a;
      
  scanf("%d %lld %d",&n,&t,&q);
  
  for(int i=0;i<n;i++){
    scanf("%lld %d",&a,&b);
    vec.push_back( (PA){a,b,LLONG_MAX});
  }
  
  for(int i=0;i<n-1;i++){
    if( vec[i].second == 1 && vec[i+1].second == 2){
      vec[i].place = (vec[i].first+vec[i+1].first)/2;
      east(i-1,vec[i].place);
      west(i+1,vec[i].place);
    }
  }

  for(int i=0;i<q;i++){
    scanf("%d",&c);
    c--;
    
    if(vec[c].place == LLONG_MAX || llabs(vec[c].first-vec[c].place) > t){
      if(vec[c].second == 1) cout << vec[c].first+t << endl;
      if(vec[c].second == 2) cout << vec[c].first-t << endl;
    } else cout << vec[c].place << endl;
  }
  return (0);
}

C++: #include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

ll a[100001];
int d[100001];
vector<ll> v;
int main(){
    ll n,t,q;
    cin>>n>>t>>q;
    int pre=2;
    v.pb(LLONG_MIN);
    rep(i,n){
        cin>>a[i]>>d[i];
        if(pre==1&&d[i]==2){
            v.pb((a[i-1]+a[i])/2);
        }
        pre=d[i];
    }
    v.pb(LLONG_MAX);
    int x;
    rep(i,q){
        cin>>x;--x;
        if(d[x]==2){
            int cur=lower_bound(v.begin(),v.end(),a[x])-v.begin();
            if(a[x]-t>v[cur-1]) cout<<a[x]-t<<endl;
            else cout<<v[cur-1]<<endl;
        }
        else{
            int cur=upper_bound(v.begin(),v.end(),a[x])-v.begin();
            if(a[x]+t<v[cur]) cout<<a[x]+t<<endl;
            else cout<<v[cur]<<endl;
        }
    }
    return 0;
}

C++: #include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const ll INF = 1ll << 60;
const int MAX_N = 100000;

ll A[MAX_N], D[MAX_N];
ll stops[MAX_N];

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

	for (int i = 0; i < N; i++) {
		cin >> A[i] >> D[i];
		stops[i] = INF;
	}

	ll s = -INF;
	if (D[0] == 2) stops[0] = s;

	for (int i = 1; i < N; i++) {

		if (D[i - 1] == 1 && D[i] == 2) {
			s = (A[i] + A[i - 1]) / 2;

			for (int j = i - 1; j >= 0 && D[j] == 1; j--)
				stops[j] = s;
		}
		
		if (D[i] == 2) stops[i] = s;
	}

	for (int i = 0; i < Q; i++) {
		ll x;
		cin >> x;
		x--;
		ll ans;
		if (D[x] == 1) ans = min(A[x] + T, stops[x]);
		else ans = max(A[x] - T, stops[x]);
		cout << ans << endl;
	}
}

C++: #include <bits/stdc++.h>
using namespace std;
int n, q, c, e, d[111111]; long long t, x[111111], y[111111];
int main() {
	scanf("%d%lld%d", &n, &t, &q);
	for (int i = 0; i < n; i++) scanf("%lld%d", x + i, d + i);
	for (int i = 1; i < n; i++) if (d[i] - d[i - 1] == 1) y[c++] = (x[i - 1] + x[i]) / 2;
	for (int i = 0; i < q; i++) {
		scanf("%d", &e); e--;
		int ptr = lower_bound(y, y + c, x[e]) - y;
		long long ret = x[e] + t * (d[e] * -2 + 3);
		if (d[e] == 1) { if (ptr != c) ret = min(ret, y[ptr]); }
		else if (--ptr != -1) ret = max(ret, y[ptr]);
		printf("%lld\n", ret);
	}
	return 0;
}