#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define ROF(i,r,l) for(int i=(r);i>=(l);i--)
int inf=1000000007;
ll infl=1000000000000000007;
ll mod=1000000007;

const int N=5007;

int d0[N];
int dy[N];

void findLocation(int n,int pos,int location[],int stype[])
{
	location[0]=pos;
	stype[0]=1;
	int mn=inf,y=-1;
	FOR(i,0,n-1)
	{
		if(i==0) continue;
		d0[i]=getDistance(0,i);
		if(d0[i]<mn)
		{
			mn=d0[i];
			y=i;
		}
	}
	location[y]=pos+d0[y];
	stype[y]=2;
	FOR(i,0,n-1)
	{
		if(i==y) continue;
		dy[i]=getDistance(y,i);
	}
	vector<pair<int,int>>L,R;
	FOR(i,1,n-1)
	{
		if(i==y) continue;
		if(dy[i]<d0[y]&&d0[i]==d0[y]+dy[i])
		{
			location[i]=location[y]-dy[i];
			stype[i]=1;
		}
		else if(d0[i]==d0[y]+dy[i]) L.pb({dy[i],i});
		else R.pb({d0[i],i});
	}
	sort(all(L));
	sort(all(R));
	vector<int>X={0},Y={y};
	for(auto [d,i]:R)
	{
		int p=d0[i]+location[0];
		int dis=getDistance(Y.back(),i);
		int q=location[Y.back()]-dis;
		debug(p,q);
		bool is=0;
		for(auto j:Y)
		{
			if(p+q==2*location[j])
			{
				is=1;
				location[i]=q;
				stype[i]=1;
			}
		}
		if(!is)
		{
			location[i]=p;
			stype[i]=2;
			Y.pb(i);
		}
	}
	for(auto [d,i]:L)
	{
		int p=dy[i]-location[0];
		int dis=getDistance(X.back(),i);
		int q=location[X.back()]+dis;
		bool is=0;
		for(auto j:Y)
		{
			if(p+q==2*location[j])
			{
				is=1;
				location[i]=q;
				stype[i]=2;
			}
		}
		if(!is)
		{
			location[i]=p;
			stype[i]=1;
			X.pb(i);
		}
	}
}