#include <bits/stdc++.h>
using namespace std;
#include "rail.h"
#define C 1
#define D 2
#define EMPTY -1
void findLocation(int n, int loc, int locs[], int typs[]) {
for (int i = 0; i < n; i++) typs[i] = EMPTY;
locs[0] = loc;
typs[0] = C;
if (n >= 2) {
vector<int> d0(n);
int xr = -1;
for (int i = 0; i < n; i++) {
if (i != 0) {
d0[i] = getDistance(0, i);
if (xr == -1 || d0[xr] > d0[i]) xr = i;
}
}
locs[xr] = locs[0] + d0[xr];
typs[xr] = D;
vector<int> dxr(n);
int xl = -1;
for (int i = 0; i < n; i++) {
if (i != xr) {
dxr[i] = getDistance(xr, i);
if (xl == -1 || dxr[xl] > dxr[i]) xl = i;
}
}
locs[xl] = locs[xr] - dxr[xl];
typs[xl] = C;
vector<int> dxl(n), rseq, lseq;
for (int i = 0; i < n; i++) {
if (i != xl) {
dxl[i] = i == 0 ? d0[xl] : d0[i] - (dxr[0] - dxr[xl]);
}
if (typs[i] == EMPTY) {
(dxl[i] < dxr[i] ? rseq : lseq).push_back(i);
}
}
for (int it = 0; it < 2; it++) {
swap(lseq, rseq);
swap(xl, xr);
swap(dxl, dxr);
for (int i = 0; i < n; i++) {
if (typs[i] != EMPTY) {
typs[i] = typs[i] == C ? D : C;
locs[i] = -locs[i];
}
}
vector<int>& seq = rseq;
sort(seq.begin(), seq.end(), [&dxl](int i, int j) { return dxl[i] < dxl[j]; });
for (int i : seq) {
int rightmost_c = xl, rightmost_d = xr;
for (int i : seq) {
if (typs[i] == C) {
if (locs[rightmost_c] < locs[i]) rightmost_c = i;
}
if (typs[i] == D) {
if (locs[rightmost_d] < locs[i]) rightmost_d = i;
}
}
assert(locs[rightmost_c] < locs[rightmost_d]);
int dr = getDistance(i, rightmost_d);
auto good = [&](int pos) {
for (int i = 0; i < n; i++) {
if (typs[i] != EMPTY && locs[i] == pos) return false;
}
if (pos > locs[rightmost_d]) {
if (dxl[i] != pos - locs[xl])
return false;
int possible_c = pos + locs[rightmost_d] - dr;
assert(possible_c % 2 == 0);
possible_c >>= 1;
if (!(locs[rightmost_c] <= possible_c && possible_c < locs[rightmost_d]))
return false;
for (int j = 0; j < n; j++) {
if (typs[j] == D && locs[j] == possible_c) return false;
}
} else {
assert(pos < locs[rightmost_d]);
int rd = rightmost_d;
for (int j = 0; j < n; j++) {
if (typs[j] == D && pos < locs[j] && locs[j] < locs[rd]) rd = j;
}
if (dxl[i] != locs[rd] - pos + locs[rd] - locs[xl])
return false;
if (dr != locs[rightmost_d] - pos)
return false;
}
return true;
};
for (int pos : {locs[xl] + dxl[i], locs[rightmost_d] - dr}) {
if (good(pos)) {
assert(typs[i] == EMPTY);
typs[i] = (locs[i] = pos) < locs[rightmost_d] ? C : D;
}
}
assert(typs[i] != EMPTY);
}
}
}
}
