#include "rail.h"
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
using namespace std;
void findLocation(signed n, signed first, signed lo[], signed sty[])
{
vector<vector<int>>dist(n, vector<int>(n));
vector<int>location(n);
vector<int>stype(n);
int minn=1e12,mini=-1;
for(int i = 1; i < n; i++) {
int d = getDistance(0,i);
if(d<minn) {minn=d; mini=i;}
}
int l=-1, maxl=0, r=-1, maxr=0;
rep(i,n)
{
if(getDistance(0,i)<getDistance(mini,i)&&maxr<getDistance(0,i))
{
maxr= getDistance(0,i);
r=i;
}
if(getDistance(mini,i)<getDistance(0,i)&&maxl<getDistance(mini,i))
{
maxl=getDistance(mini,i);
l=i;
}
}
if(l==-1) l=0;
if(r==-1) r=mini;
stype[0]=1;
stype[mini]=2;
location[0]=first;
location[mini]=first+getDistance(0,mini);
stype[r]=2;
stype[l]=1;
location[l]=location[mini]-getDistance(l,mini);
location[r]=location[0]+getDistance(0,r);
rep(i,n) {
if(i==0||i==mini||i==r||i==l) continue;
int d0 = getDistance(i,0), dmini = getDistance(i,mini);
if(dmini<d0)
{
if(getDistance(i,l)+getDistance(l,mini)==dmini)
{
stype[i]=2;
location[i]=location[l]+getDistance(i,l);
} else {
stype[i]=1;
location[i]=location[mini]-dmini;
}
} else
{
if(getDistance(i,r)+getDistance(r,0)==d0)
{
stype[i]=1;
location[i]=location[r]-getDistance(i,r);
} else {
stype[i]=2;
location[i]=location[0]+d0;
}
}
}
rep(i,n) sty[i]=stype[i];
rep(i,n) lo[i]=location[i];
}
