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 <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<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;

ll n, t, q, a[100000], di[100000], x[1000];
ll d[100001], dcounter = 0, time[100000];

int main() {
  scanf("%lld%lld%lld", &n, &t, &q);
  for (ll i = 0; i < n; i++) scanf("%lld%lld", &a[i], &di[i]);
  for (ll i = 0; i < q; i++) scanf("%lld", &x[i]);
  for (ll i = 0; i < n - 1; i++) if (di[i] == 1 && di[i+1] == 2) d[dcounter++] = (a[i] + a[i + 1]) / 2;
  ll temp = 0;
  for (ll i = 0; i < n; i++) {
    if (di[i] == 1) {
      if (temp != dcounter && a[i] > d[temp]) temp++;
      if (temp == dcounter) time[i] = -1;
      else time[i] = d[temp] - a[i];
    } else {
      if (dcounter > 0 && a[i] < d[0]) time[i] = -1;
      else time[i] = a[i] - d[temp];
    }
  }
  for (ll i = 0; i < q; i++) {
    int num = x[i] - 1;
    if (time[num] == -1) {
      if (di[num] == 1) printf("%lld\n", a[num] + t);
      else printf("%lld\n", a[num] - t);
      continue;
    }
    if (di[num] == 1) printf("%lld\n", a[num] + min(t, time[num]));
    else printf("%lld\n", a[num] - min(t, time[num]));
  }
}

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

int main(){
        ll n, t, q;
        scanf("%lld %lld %lld", &n, &t, &q);

        vector<ll> dist(n+2);
        dist[0] = -3e18;
        dist[n+1] = 3e18;
        vector<ll> vect(n+2);
        vect[0] = 1;
        vect[n+1] = 2;

        vector<ll> talkin(0);
        vector<ll> talkinin(n+2);
        talkinin[0] = 0;

        ll inin = 0;
        bool flag=false;
        for(ll i=1; i<n+1; i++){
                scanf("%lld %lld", &dist[i], &vect[i]);
                if(vect[i-1]==1 and vect[i]==2)talkin.push_back((dist[i-1]-dist[i])/2+dist[i]);
                if(vect[i-1]==2 and vect[i]==1) inin++;

                talkinin[i] = inin;
        }
        if(vect[n]==1)talkin.push_back((dist[n]-dist[n+1])/2+dist[n+1]);
        for(int i=0; i<n+2; i++) talkinin[i] = talkin[talkinin[i]];

        vector<ll> imp(q);
        for(int i=0; i<q; i++) scanf("%lld", &imp[i]);
        for(int i=0; i<q; i++){
                ll m = imp[i];
                if(vect[m]==1) cout << min(dist[m]+t, talkinin[m]) << endl;
                else cout << max(dist[m]-t, talkinin[m]) << endl;
        }
        return 0;
}

C++: #include<bits/stdc++.h>
#define int long long int
#define MP make_pair
#define PB push_back
#define F first
#define S second
using namespace std;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef vector<PII> VP;

const int INF = 4e18;

int n, t, q;
int a[100010], d[100010], x[1010], ans[1010];

int stoppoint(int who)
{
  if(d[who] == 1){
    if(d[who + 1] == 2){
      return (a[who] + a[who + 1]) / 2;
    }
    else{
      return stoppoint(who + 1);
    }
  }
  else{
    if(d[who - 1] == 1){
      return (a[who] + a[who - 1]) / 2;
    }
    else{
      return stoppoint(who - 1);
    }
  }
}

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

  a[0] = -INF, d[0] = 1;
  a[n + 1] = INF, d[n + 1] = 2;

  for(int i = 1; i <= q; i++){
    int stp = stoppoint(x[i]);

    if(abs(a[x[i]] - stp) <= t){
      ans[i] = stp;
    }
    else{
      if(d[x[i]] == 1){
	ans[i] = a[x[i]] + t;
      }
      else{
	ans[i] = a[x[i]] - t;
      }
    }
  }

  for(int i = 1; i <= q; i++){
    printf("%lld\n", ans[i]);
  }
  return 0;
}

C++: #include <vector>
#include <iostream>
#include <algorithm>
#pragma warning(disable : 4996)
using namespace std;
typedef long long ll;
int N, Q, x, d[100009]; ll T, a[100009];
int main() {
	scanf("%d%lld%d", &N, &T, &Q);
	for (int i = 0; i < N; i++) scanf("%lld%d", &a[i], &d[i]);
	vector<ll> v;
	for (int i = 0; i < N - 1; i++) {
		if (d[i] == 1 && d[i + 1] == 2) v.push_back((a[i] + a[i + 1]) >> 1);
	}
	for (int i = 0; i < Q; i++) {
		scanf("%d", &x); x--;
		int ptr = lower_bound(v.begin(), v.end(), a[x]) - v.begin();
		if (d[x] == 2) ptr--;
		ll e = a[x] + T * (d[x] == 1 ? 1 : -1), ret;
		if (0 <= ptr && ptr < v.size()) {
			if (d[x] == 1) ret = min(e, v[ptr]);
			else ret = max(e, v[ptr]);
		}
		else ret = e;
		printf("%lld\n", ret);
	}
	return 0;
}

C++: #include<cstdio>
#include<algorithm>
#include<functional>
#include<cstring>
#include<iostream>
using namespace std;
int main(void)
{
	int N,T,Q,house[100001],muki[100001];
	int X[1001];
	int list[100001];
	int i,j;
	cin>>N>>T>>Q;
	for(i=1;i<=N;i++) cin>>house[i]>>muki[i];
	for(i=1;i<=Q;i++) cin>>X[i];
	for(i=N;i>=1;i--) {
		if(muki[i]==2) continue;
		if(i==N) list[i]=house[i]+T;
		else if(muki[i+1]==2) list[i]=min(house[i]+T,(house[i]+house[i+1])/2);
		else list[i]=min(house[i]+T,list[i+1]);
	}
	for(i=1;i<=N;i++) {
		if(muki[i]==1) continue;
		if(i==1) list[i]=house[i]-T;
		else if(muki[i-1]==1) list[i]=max(house[i]-T,(house[i]+house[i-1])/2);
		else list[i]=max(house[i]-T,list[i-1]);
	}
	for(i=1;i<=Q;i++) {
		cout<<list[X[i]]<<endl;
	}
	return 0;
}