#include "rail.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for(ll i = ll(n) - 1; i >= 0; --i)
#define rrep2(i, n, t) for(ll i = ll(n) - 1; i >= ll(t); --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;
template<class T>
bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T>
bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
void findLocation(int n, int first, int location[], int stype[]) {
if (n == 1) {
location[0] = first;
stype[0] = 1;
return;
}
vi dl(n), dr(n);
rep2(i, 1, n) dl[i] = getDistance(0, i);
int r = min_element(dl.begin() + 1, dl.end()) - dl.begin();
location[r] = first + dl[r];
stype[r] = 2;
rep(i, n) if (i != r) dr[i] = getDistance(r, i);
int l = 0;
rep(i, n) if (i != r and dr[i] < dr[l]) l = i;
location[l] = location[r] - dr[l];
stype[l] = 1;
if (l) {
int x = dl[l];
dl[0] = x + dr[l] * 2;
dl[l] = 0;
rep2(i, 1, n) if (i != l) dl[i] -= x;
}
auto f = [&](const vi &v) {
int now = r;
for (int i: v) {
int d = getDistance(now, i);
if (dl[now] + dl[i] == d) {
location[i] = dl[i];
stype[i] = 2;
now = i;
} else {
location[i] = dl[now] - d;
stype[i] = 1;
}
}
};
vi a, b;
rep(i, n) {
if (i == l or i == r) continue;
if (dl[i] < dr[i]) a.pb(i);
else b.pb(i);
}
rep(_, 2) {
f(a);
swap(l, r);
swap(dl, dr);
swap(a, b);
}
for (int i: a) location[i] += location[l];
for (int i: b) {
location[i] = location[r] - location[i];
stype[i] = 3 - stype[i];
}
}
