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 <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>

using namespace std;

#define int long long

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define omajinai ios::sync_with_stdio(false);cin.tie(0)
#define rep(i,x) for(int i=0;i<(int)(x);++i)
#define rep1(i,x) for(int i=1;i<=(int)(x);++i)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

template<typename T>T& max(T&a,T&b){if(a>=b)return a;return b;}
template<typename T>T& min(T&a,T&b){if(a<b)return a;return b;}
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>T get(){T a;cin>>a;return a;}
template<typename T>T rev(T a){reverse(all(a));return a;}
template<typename T>vector<T>&sort(vector<T>&a){sort(all(a));return a;}

const int inf = 1e9;
const ll linf = 3e18;
const double eps = 1e-9;

int A[100010], D[100010];

vector<int> kabe;

signed main()
{
	omajinai;

	int N, T, Q; cin >> N >> T >> Q;

	rep(i, N) {
		cin >> A[i] >> D[i];
	}

	rep(i, N - 1) {
		if (D[i] == 1 && D[i + 1] == 2) {
			kabe.PB((A[i] + A[i + 1]) / 2);
		}
	}

	rep(i, Q) {
		int x; cin >> x;
		-- x;

		if (D[x] == 1) {
			vi::iterator itr = upper_bound(all(kabe), A[x]);
			if (itr == kabe.end()) {
				cout << A[x] + T << endl;
			} else {
				cout << min(A[x] + T, *itr) << endl;
			}
		} else {
			vi::iterator itr = lower_bound(all(kabe), A[x]);

			if (itr == kabe.begin()) {
				cout << A[x] - T << endl;
			} else {
				itr -= 1;
				cout << max(A[x] - T, *itr) << endl;
			}
		}
	}
}

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<=2*T){
            dummy=(house[i].place+house[i+1].place)/2;
            house[i].place=dummy;
            house[i+1].place=dummy;
            for(int j=i-1;j>=1;--j){
                if(house[j+1].place-house[j].place<=T&&house[j].dotti==1){
                    house[j].place=house[j+1].place;
                    house[j].dotti=3;
                }else{
                    break;
                }
            }
            for(int j=i+2;j<=n;++j){
                if(house[j].place-house[j-1].place<=T&&house[j].dotti==2){
                    house[j].place=house[j-1].place;
                    house[j].dotti=3;
                }else{
                    break;
                }
            }
        }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){
            house[i].place-=T;
        }else if(house[i].dotti==1){
            house[i].place+=T;
        }
    }
    int doll;
    for(int i=0;i<Q;++i){
        cin>>doll;
        cout<<house[doll].place<<endl;
    }
    return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <climits>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

int N, Q;
long long T;
long long A[100010];
bool dir[100010];
long long st[100010];

long long query(int i) {
  if (st[i] != -1) return st[i];
  long long ans;
  // ->
  if (dir[i]) {
    if (i == N-1)      ans = 0;
    else if (dir[i+1]) {
      int t = query(i+1);
      if (t == 0) ans = 0;
      else        ans = (A[i+1] - A[i]) + t;
    }
    else               ans = (A[i+1] - A[i]) / 2;
  }
  // <-
  else {
    if (i == 0)        ans = 0;
    else if (dir[i-1]) ans = (A[i] - A[i-1]) / 2;
    else {
      int t = query(i-1);
      if (t == 0) ans = 0;
      else        ans = (A[i] - A[i-1]) + t;
    }
  }
  return st[i] = ans;
}

int main() {
  cin >> N >> T >> Q;
  for (int i=0; i<N; i++) {
    int d;
    cin >> A[i] >> d;
    if (d == 1) dir[i] = true;
    st[i] = -1;
  }

  query(3);
  for (int i=0; i<Q; i++) {
    int x;
    cin >> x;
    long long t = query(x-1);
    cout << A[x-1] + (t == 0 ? T : min(t, T))*(dir[x-1]?1:-1) << "\n";
  }
  return 0;
}

C++: #include<iostream>
#include<fstream>

using namespace std;
signed long long int a[100000];
signed long long int b[100000];
signed long long int c[100000];
signed long long int d[100000];
signed long long int e[100000];
signed long long int x=0;
signed long long int h[100000];
signed long long int n=0;
signed long long int t=0;
signed long long int q=0;
signed long long int i=0;
signed long long int j=0;
signed long long int k=0;
signed long long int s=0;
signed long long int f=0;
int main(){
	
	for(i=0;i<100000;i++){
		a[i]=0;
		b[i]=0;
		c[i]=0;
		d[i]=0;
		e[i]=0;
		h[i]=0;
	}
	cin>>n;
	cin>>t;
	cin>>q;
	for(i=0;i<n;i++){
		cin>>a[i];
		cin>>b[i];
	}
	for(i=0;i<q;i++){
		cin>>d[i];
	}
	for(i=0;i<n-1;i++){
		if(b[i]==1 && b[i+1]==2){
			f=a[i+1]-a[i];
			f=f/2;
			c[i]=f;
			c[i+1]=f;
			x=f+a[i];
			if(s!=0){
				for(j=0;j<s;j++){
					c[h[j]]=x-a[h[j]];
				}
			}
			s=0;			
		}else if(b[i]==1){
			h[s]=i;
			s++;
		}else if(b[i+1]==2){
			c[i+1]=a[i+1]-x;
			if(c[i+1]<0){
				c[i+1]=0;
			}
		}
	}
	for(i=0;i<q;i++){
		if(c[d[i]-1]==0 || c[d[i]-1]>t){
			if(b[d[i]-1]==1){
				e[i]=a[d[i]-1]+t;
			}else{
				e[i]=a[d[i]-1]-t;
			}
		}else{
			if(b[d[i]-1]==1){
				e[i]=a[d[i]-1]+c[d[i]-1];
			}else{
				e[i]=a[d[i]-1]-c[d[i]-1];
			}
		}
		cout<<e[i]<<endl;
	}
}