#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef pair<int,int> pii;
int dis[5005][5005],minind,ind[2000002];
void findLocation(int n, int first, int location[], int stype[])
{
location[0]=first;
stype[0]=1;
if(n==1)return ;
for(int i=1;i<n;i++)
{
dis[0][i]=dis[i][0]=getDistance(0,i);
if(!minind || dis[0][minind]>dis[0][i])minind=i;
}
int c0,d0;
d0=minind;
location[d0]=location[0]+dis[0][d0];
stype[d0]=2;
minind=d0;
for(int i=0;i<n;i++)
{
if(i==d0)continue;
dis[d0][i]=dis[i][d0]=getDistance(d0,i);
if(minind==d0 || dis[d0][minind]>dis[d0][i])minind=i;
}
c0=minind;
location[c0]=location[d0]-dis[d0][c0];
stype[c0]=1;
for(int i=0;i<n;i++)
{
if(i==0 || i==c0 || i==d0)continue;
dis[c0][i]=dis[0][i]-(dis[0][d0]-dis[c0][d0]);
}
vector<pii>ri,le;
for(int i=0;i<n;i++)
{
if(i==c0 || i==d0)continue;
if(dis[c0][i]<dis[d0][i])ri.push_back({dis[c0][i],i});
else le.push_back({dis[d0][i],i});
}
sort(ri.begin(),ri.end());
sort(le.begin(),le.end());
//right
int sum;
vector<pii>D;
memset(ind,-1,sizeof(ind));
sum=location[d0]-location[c0];
D.push_back({sum,d0});
ind[sum]=sz(D)-1;
for(auto &x:ri)
{
int dis=x.first;
int i=x.second;
int j=sz(D)-1;
int ch=0;
int dis2=getDistance(D[j].second,i);
if((sum+dis-dis2)%2==0 && sum+dis-dis2>0 && ind[(sum+dis-dis2)/2]!=-1)
{
int k=ind[(sum+dis-dis2)/2];
if(k>0 && D[k].first-D[k-1].first>dis2-sum+D[k].first)
{
ch=1;
location[i]=location[D[k].second]-dis2+sum-D[k].first;
stype[i]=1;
}
}
if(ch==0)
{
location[i]=location[c0]+dis;
stype[i]=2;
sum=location[i]-location[c0];
D.push_back({sum,i});
ind[sum]=sz(D)-1;
}
}
//left
sum=0;
vector<pii>C;
memset(ind,-1,sizeof(ind));
sum=location[d0]-location[c0];
C.push_back({sum,c0});
ind[sum]=sz(C)-1;
for(auto &x:le)
{
int dis=x.first;
int i=x.second;
int j=sz(C)-1;
int ch=0;
int dis2=getDistance(C[j].second,i);
if((sum+dis-dis2)%2==0 && sum+dis-dis2>0 && ind[(sum+dis-dis2)/2]!=-1)
{
int k=ind[(sum+dis-dis2)/2];
if(k>0 && C[k].first-C[k-1].first>dis2-sum+C[k].first)
{
ch=1;
location[i]=location[C[k].second]+dis2-sum+C[k].first;
stype[i]=2;
}
}
if(ch==0)
{
location[i]=location[d0]-dis;
stype[i]=1;
sum=location[d0]-location[i];
C.push_back({sum,i});
ind[sum]=sz(C)-1;
}
}
return ;
}
