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>
using namespace std;
#pragma GCC optimize("Ofast")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define INF LLONG_MAX - 100
#define MOD 1000000007
#define fcout cout << fixed << setprecision(15)
#define int long long
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
#define lower_bound lowb
#define upper_bound upb
typedef long long ll;
typedef pair<int, int> P;
typedef priority_queue<int> pque;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a*b/gcd(a,b);};
int mod(int a,int b){return (a+b-1)/b;};
int month[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;};
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;};

int N, T, Q;
int a[1000010], d[1000010];
int x[1000010];
int memo[1000010];

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> T >> Q;
	rep(i, N) cin >> a[i] >> d[i];
	rep(i, Q) cin >> x[i];
	Fill(memo, INF);

	rep(i, N - 1) {
		if(d[i] == 1 && d[i + 1] == 2) {
			int t = (a[i] + a[i + 1]) / 2;

			memo[i] = t;

			for(int j = i - 1; ((d[j] == 1) && (j >= 0)); j--) {
				memo[j] = t;
			}

			for(int j = i + 1; ((d[j] == 2) && (j < N)); j++) {
				memo[j] = t;
			}
		}
	}

	rep(i, Q) {
		int now = x[i] - 1;
		if(abs(a[now] - memo[now]) <= T) cout << memo[now] << endl;
		else if(d[now] == 1) cout << a[now] + T << endl;
		else cout << a[now] - T << endl;
	}
	return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)

typedef long long ll;
typedef pair<ll, ll> pll;

int main() {
	ll n, t, q;
	cin >> n >> t >> q;
	vector<pll> data(n);
	
	REP(i, n) scanf("%lld%lld", &data[i].first, &data[i].second);
	sort(data.begin(), data.end());
	
	vector<ll> sto;
	REP(i, n - 1) {
		if (data[i].second == 1 && data[i + 1].second == 2) {
			sto.push_back((data[i].first + data[i + 1].first) / 2);
		}
	}
	sort(sto.begin(), sto.end());
	
	REP(i, q) {
		int now;
		scanf("%d", &now);
		now--;
		
		ll ans;
		if (data[now].second == 1) {
			ans = data[now].first + t;
			REP(j, sto.size()) {
				if (data[now].first < sto[j])
					ans = min(ans, sto[j]);
			}
		}
		else {
			ans = data[now].first - t;
			REP(j, sto.size()) {
				if (sto[j] < data[now].first)
					ans = max(ans, sto[j]);
			}
		}
		
		printf("%lld\n", ans);
	}
	
	return 0;
}

C++: #include<iostream>
#include<cmath>
using namespace std;
long long N, T, Q, a[1 << 17], b[1 << 17], c[1 << 17];
int main() {
	cin >> N >> T >> Q;
	for (int i = 0; i < N; i++)cin >> a[i] >> b[i];
	long long H = -1LL << 62;
	for (int i = 0; i < N; i++) {
		if (b[i] == 2) {
			if (i >= 1) {
				if (b[i - 1] == 1) {
					long long C = (a[i - 1] + a[i]) / 2;
					if (abs(C - a[i]) <= T) { H = C; c[i] = C; }
					else { c[i] = a[i] - T; }
				}
				else {
					if (abs(H - a[i]) <= T)c[i] = H;
					else { c[i] = a[i] - T; }
				}
			}
			if (i == 0)c[i] = a[i] - T;
		}
	}
	H = 1LL << 62;
	for (int i = N - 1; i >= 0; i--) {
		if (b[i] == 1) {
			if (i < N - 1) {
				if (b[i + 1] == 2) {
					long long C = (a[i + 1] + a[i]) / 2;
					if (abs(C - a[i]) <= T) { H = C; c[i] = C; }
					else { c[i] = a[i] + T; }
				}
				else {
					if (abs(H - a[i]) <= T)c[i] = H;
					else { c[i] = a[i] + T; }
				}
			}
			if (i == N - 1)c[i] = a[i] + T;
		}
	}
	for (int i = 0; i < Q; i++) {
		int p; cin >> p; p--; cout << c[p] << endl;
	}
	return 0;
}

C++: #include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<unordered_map>
using namespace std;
typedef long long ll;
struct H {
	ll place, go;
};
H h[100001];
ll p[100001];
int main() {
	ll n, t, q;
	while (cin >> n >> t >> q) {
		for (ll i = 1; i <= n; i++) {
			cin >> h[i].place >> h[i].go;
			p[i] = 0;
		}
		vector<ll>v;
		for (ll i = 1; i < n; i++) {
			if (h[i].go == 1 && h[i + 1].go == 2) {
				if ((h[i].place + h[i + 1].place) / 2 - h[i].place <= t) {
					p[i] = (h[i].place + h[i + 1].place) / 2;
					p[i + 1] = p[i];
					v.push_back(p[i + 1]);
				}
			}
		}
		sort(v.begin(), v.end());
		for (ll i = 1; i <= n; i++) {
			if (p[i] == 0) {
				ll k;
				if (h[i].go == 1) {
					k = lower_bound(v.begin(), v.end(), h[i].place) - v.begin();
				}
				else {
					k = lower_bound(v.begin(), v.end(), h[i].place) - v.begin();
					ll s=0, e=(ll)v.size(), t2;
					while (e - s > 1) {
						t2 = (e + s) / 2;
						if (v[t2] <= h[i].place) e = t2;
						if (v[t2] > h[i].place)s = t2;
					}
					if (e < (ll)v.size()&&v[e] <= h[i].place)
						k = e;
					else 
						k = s;
				}
				if (k < v.size() && max(v[k] - h[i].place, 0 - (v[k] - h[i].place)) <= t)
					p[i] = v[k];
				else {
					if (h[i].go == 1)p[i] = h[i].place + t;
					else p[i] = h[i].place - t;
				}
			}
		}
		for (ll i = 0; i < q; i++) {
			ll o;
			cin >> o;
			cout << p[o] << endl;
		}
	}
}