#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define TCASES int t; cin >> t; while(t--)
// #define DEBUG
// #define AUTO_INTERACTOR
#ifndef DEBUG
#include "rail.h"
#endif
int n;
#ifdef DEBUG
vi a_loc;
vi a_type;
int getDistance(int i, int j) {
#ifdef AUTO_INTERACTOR
cout << i << " " << j << endl;
int ans;
int loc_i = a_loc[i], loc_j = a_loc[j];
if(loc_i > loc_j) {
swap(loc_i, loc_j);
swap(i, j);
}
// Now, i is to the left of j
int typei = a_type[i], typej = a_type[j];
if(typei == 1 && typej == 2) {
ans = loc_j - loc_i;
} else if (typei == 1 && typej == 1) {
// Find the leftmost D that is to the right of both
int leftmost_d_pos = numeric_limits<int>::max();
LI(_i, 0, n) {
if(a_loc[_i] > loc_j && a_type[_i] == 2 && a_loc[_i] < leftmost_d_pos) leftmost_d_pos = a_loc[_i];
}
ans = (leftmost_d_pos << 1) - (loc_i + loc_j);
} else if(typei == 2 && typej == 2) {
// Find the rightmost C that is to the left of both
int rightmost_c_pos = numeric_limits<int>::min();
LI(_i, 0, n) {
if(a_loc[_i] < loc_i && a_type[_i] == 1 && a_loc[_i] > rightmost_c_pos) rightmost_c_pos = a_loc[_i];
}
ans = (loc_i + loc_j) - (rightmost_c_pos << 1);
} else {
int leftmost_d_pos = numeric_limits<int>::max();
int rightmost_c_pos = numeric_limits<int>::min();
LI(_i, 0, n) {
if(a_loc[_i] > loc_j && a_type[_i] == 2 && a_loc[_i] < leftmost_d_pos) leftmost_d_pos = a_loc[_i];
if(a_loc[_i] < loc_i && a_type[_i] == 1 && a_loc[_i] > rightmost_c_pos) rightmost_c_pos = a_loc[_i];
}
ans = ((rightmost_c_pos - leftmost_d_pos) << 1) - (loc_j - loc_i);
}
cout << ans << endl;
return ans;
#endif
#ifndef AUTO_INTERACTOR
cout << i << " " << j << endl;
int ans;
cin >> ans;
return ans;
#endif
}
#endif
void findLocation(int n, int first, int location[], int stype[]) {
LI(i, 0, n) {stype[i] = 0; location[i] = -1;}
location[0] = first;
stype[0] = 1;
if(n == 1) return; // Special case: if there's only one station, exit
// Get the distances from station zero
// Get the minimum distance, that will be a type 2 block
vpi d0;
d0.push_back({0, 0});
int stx = 0;
int mindist0 = numeric_limits<int>::max();
LI(i, 1, n) {
d0.push_back({getDistance(0, i), i});
if(d0[i].fi < mindist0) {
mindist0 = d0[i].fi;
stx = i;
}
}
location[stx] = first + mindist0;
stype[stx] = 2;
vpi d0sorted = d0;
sort(d0sorted.begin(), d0sorted.end());
// Getting distances from station X
vpi dx;
LI(i, 0, n) {
if(i == stx) {
dx.push_back({0, i});
continue;
}
dx.push_back({getDistance(stx, i), i});
}
// Now we have ((--)
/*
(---)--(((--[(--]--)(--))
(---(--)-)[]
*/
int sty = stx;
int styl = 0; // leftmost C-type
LI(_i, 0, n) {
int i = d0sorted[_i].se;
if(i == 0 || i == stx) continue;
if(dx[i].fi < dx[0].fi && d0[i].fi == d0[stx].fi + dx[i].fi) {
// Station Z is between 0 and x
location[i] = first + d0[stx].fi - dx[i].fi;
stype[i] = 1;
#ifdef DEBUG
cout << "MIDCASE " << i << endl;
#endif
} else if(d0[i].fi == dx[i].fi + d0[stx].fi) {
// Station Z is to the left of 0: literally just mirror the logic below
int distzy = getDistance(i, styl);
int deflect_st_block = location[styl] - ((dx[i].fi - dx[styl].fi - distzy) >> 1);
int typeof_dst = 0;
LI(j, 0, n) {
if(location[j] == deflect_st_block) {
typeof_dst = stype[j];
break;
}
}
if(typeof_dst == 1) {
// Deflector is of C-type, thus, the current station is
// of type D
location[i] = location[styl] + distzy;
stype[i] = 2;
} else {
// Deflector is of D-type, thus the current station is of type C
location[i] = first + dx[0].fi - dx[i].fi;
stype[i] = 1;
styl = i;
}
} else {
// Station Z is to the right
int distzy = getDistance(i, sty);
int deflect_st_block = location[sty] + ((d0[i].fi - d0[sty].fi - distzy) >> 1);
int typeof_dst = 0;
LI(j, 0, n) {
if(location[j] == deflect_st_block) {
typeof_dst = stype[j];
break;
}
}
if(typeof_dst == 2) {
// Deflector is of D-type, thus, the current station is
// of type C
location[i] = location[sty] - distzy;
stype[i] = 1;
} else {
// Deflector is of C-type, thus the current station is of type D
location[i] = first + d0[i].fi;
stype[i] = 2;
sty = i;
}
}
}
// ok we're done!
}
#ifdef DEBUG
int main() {
cin >> n;
#ifndef AUTO_INTERACTOR
int first;
cin >> first;
#endif
#ifdef AUTO_INTERACTOR
LI(i, 0, n) {
char c; int loc;
cin >> c >> loc;
a_type.push_back(c == 'C' ? 1 : 2);
a_loc.push_back(loc);
}
#endif
#ifdef AUTO_INTERACTOR
int first = a_loc[0];
#endif
vi location(n, 0);
vi stype(n, 0);
findLocation(n, first, &location[0], &stype[0]);
cout << "THE ANSWER" << endl;
L(i, 0, n) {
#ifndef AUTO_INTERACTOR
cout << i << " " << (stype[i] == 1 ? "C" : "D") << " " << location[i] << endl;
#endif
#ifdef AUTO_INTERACTOR
cout << (stype[i] == 1 ? "C" : "D") << " " << location[i] << endl;
#endif
}
return 0;
}
#endif
