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<vector>
#include<algorithm>
using namespace std;
 
typedef long long LL;
typedef pair<LL, LL> P;
 
int main() {
    LL a, c;
    LL b;
    cin >> a >> b >> c;
 
    P m[100005];
    P q[1010];
    vector<LL>st;
 
    for (LL i = 0;i < a;i++)cin >> m[i].first >> m[i].second;
    
    for (LL i = 0;i < c;i++) {
        LL d;
        cin >> d;
        q[i] = m[d - 1];
    }
 
    for (LL i = 0;i < a - 1;i++) {
        if (m[i].second == 1 && m[i + 1].second == 2)st.push_back((m[i].first + m[i+1].first) / 2);
    }
 
    for (LL i = 0;i < c;i++) {
 
        if (q[i].second == 1) {
 
            long long e = q[i].first+b;;
 
            for (int j = 0;j < st.size();j++) {
 
                if (q[i].first < st[j]) {
                    if (q[i].first + b >= st[j])e = st[j];
                }
 
            }
            cout << e << endl;
        }
 
        else {
 
            long long e=q[i].first-b;
 
            LL f = st.size();
            for (LL j = f - 1;j > -1;j--) {
 
                if (q[i].first > st[j]) {
                    if (q[i].first - b <= st[j])e = st[j];
                }
                 
            }
            cout << e << endl;
        }
    }
   
    return 0;
}

C++: #include <cstdio>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;

int n, q;
long long int t;
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 %lld %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<set>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

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

    ll d, a;
    vector<pair<ll,int>> x;
    vector<pair<ll,int>> v[2]; // 0-right, 1-left
    for(int i = 0; i < n; i++){
        cin >> d >> a;
        a--;
        v[a].push_back({d,i});
        x.push_back({d,a});
    }

    sort(v[0].begin(), v[0].end());
    sort(v[1].begin(), v[1].end());

    priority_queue<pair<ll,pii>, vector<pair<ll,pii>>, greater<pair<ll,pii>>> pq;
    for(pair<ll,int> p : v[0]){
        auto it = lower_bound(v[1].begin(), v[1].end(), p);
        if(it == v[1].end())    continue;
        pq.push({(*it).first-p.first, {p.second, (*it).second}});
    }

    set<ll> fixed;
    while(!pq.empty()){
        auto p = pq.top();  pq.pop();
        int l = p.second.first, r = p.second.second;
        ll dist = p.first;
        if(dist/2 > t)  break;
        auto itl = fixed.lower_bound(x[l].first), itr = fixed.lower_bound(x[r].first-dist/2);
        bool lb = itl == fixed.end() || *itl > x[l].first+dist/2;
        bool rb = itr == fixed.end() || *itr > x[r].first;
        if(lb && rb){
            fixed.insert(dist/2+x[l].first);
        }
    }

    int ask;
    for(int i = 0; i < q; i++){
        cin >> ask;
        ask--;
        if(x[ask].second == 0){
            auto it = fixed.lower_bound(x[ask].first);
            if(it == fixed.end() || *it > x[ask].first+t){
                cout << x[ask].first+t << endl;
            }else{
                cout << *it << endl;
            }
        }else{
            auto it = fixed.lower_bound(x[ask].first);
            if(it != fixed.begin()) it--;
            if(fixed.empty() || *it > x[ask].first || *it < x[ask].first-t){
                cout << x[ask].first-t << endl;
            }else{
                cout << *it << endl;
            }
        }
    }

    return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#define ll long long
using namespace std;
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	ll N, T, Q; cin >> N >> T >> Q;
	vector <pair<ll, ll>> A(N + 1);
	for (int i = 1; i <= N; i++) {
		cin >> A[i].first >> A[i].second;
		if (A[i].second == 2) A[i].second = -1;
	}
	vector<ll> q(Q);
	for (int i = 0; i < Q;i++) cin >> q[i];


	vector<ll> ans(N + 1);
	int f = 0;
	ll l;
	ll mid;
	for (int i = 1; i <= N;i++) {
		if (f == 0 && A[i].second == -1) {
			ans[i] = A[i].first + A[i].second*T;
			continue;
		}
		if (f == 0 && A[i].second == 1) {
			f = 1; l = i;
			continue;
		}
		if (f == 1 && A[i].second == 1) continue;
		if (f == 1 && A[i].second == -1) {
			mid = (A[i].first + A[i - 1].first) / 2;
			ans[i] = max(mid, A[i].first + A[i].second * T);

			for (int at = l; at < i; at++) {
				ans[at] = min(mid, A[at].first + A[at].second*T);
			}
			f = 2;
			continue;
		}
		if (f == 2 && A[i].second == -1) {
			ans[i] = max(mid, A[i].first + A[i].second*T);
			continue;
		}
		if (f == 2 && A[i].second == 1) {
			f = 1; l = i;
			continue;
		}
	}
	if (f == 1) {
		//ans[N] = A[N].first + A[N].second*T;
		for (int at = l; at <= N; at++) {
			ans[at] = A[at].first + A[at].second*T;
		}
	}

	for (int i = 0; i < Q;i++) {
		cout << ans[q[i]] << endl;
	}
}