#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
refs:
http://blog.brucemerry.org.za/2014/07/ioi-2014-day-1-analysis.html
*/
const int MOD = 1e9 + 7;
const int N = 5e3 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
#include "rail.h"
int dp[N][N];
int q = 0;
int currn;
int d(int i, int j){
if(i == j) return 0;
if(i > j) swap(i,j);
if(dp[i][j] != -1){
return dp[i][j];
}
q++;
// assert(q <= currn*(currn-1)/2);
return dp[i][j] = getDistance(i,j);
}
void findLocation(int n, int first_loc, int location[], int stype[])
{
rep(i,n){
location[i] = -1;
stype[i] = -1;
}
memset(dp,-1,sizeof dp);
currn = n;
location[0] = first_loc;
stype[0] = 1;
if(n == 1) return;
// order by dis from first
int first = 0;
vector<pii> dis;
rep(i,n){
dis.pb({d(first,i),i});
}
sort(all(dis));
// find the ()
int first_close = dis[1].ss;
location[first_close] = first_loc+dis[1].ff;
stype[first_close] = 2;
// find all to the left (path from first to i must pass through first_close)
// guys not on left must be on right
vector<pii> to_left, to_right;
rep(i,n){
if(i == first or i == first_close) conts;
if(d(first,i) == d(first,first_close)+d(first_close,i)){
to_left.pb({d(first_close,i),i});
}
else{
to_right.pb({d(first,i),i});
}
}
sort(all(to_left)), sort(all(to_right));
auto find_station = [&](int pos){
rep(i,n){
if(location[i] == pos){
return i;
}
}
return -1;
};
// identify the types and locations of all guys to the left
int l = first;
for(auto [dis,i] : to_left){
int val = d(l,i)+d(first_close,i)-d(l,first_close);
assert(!(val&1));
val /= 2;
int pos = location[l]+d(l,i)-val;
// if there is a station at location = pos with type(station) = C, then type(i) = D
// otherwise, type(i) = C
int station = find_station(pos);
if(station != -1 and stype[station] == 1){
location[i] = location[station]+val;
stype[i] = 2;
}
else{
location[i] = location[first_close]-d(first_close,i);
stype[i] = 1;
l = i;
}
}
// identify the types and locations of all guys to the right
int r = first_close;
for(auto [dis,i] : to_right){
int val = d(r,i)+d(first,i)-d(first,r);
assert(!(val&1));
val /= 2;
int pos = location[r]-d(r,i)+val;
// if there is a station at location = pos with type(station) = D, then type(i) = C
// otherwise, type(i) = D
int station = find_station(pos);
if(station != -1 and stype[station] == 2){
location[i] = location[station]-val;
stype[i] = 1;
}
else{
location[i] = location[first]+d(first,i);
stype[i] = 2;
r = i;
}
}
}
