#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,int> mp;
const int INF = 1e9;
int getd(int x, int y)
{
if(x==y)
return 0;
if(x<0 || y<0)
return INF;
if(x>y)
swap(x,y);
if(mp[{x,y}]==0)
mp[{x,y}] = getDistance(x,y);
return mp[{x,y}];
}
void findLocation(int N, int first, int location[], int stype[])
{
mp.clear();
location[0] = first;
stype[0] = 1;
int le=0,ri=-1;
while(1)
{
int ble=-1,bri=-1;
for(int i=0;i<N;i++)
{
if(stype[i]!=0)
continue;
if(ble==-1 || getd(le,i) < getd(le,ble))
ble = i;
if(bri==-1 || getd(ri,i) < getd(ri,bri))
bri = i;
}
if(ble==-1)
break;
if(getd(le,ble) <= getd(ri,bri))
{
stype[ble] = 2;
location[ble] = location[le] + getd(le,ble);
//assert(getd(le,ble) > getd(le,ri));
for(int i=0;i<N;i++)
{
if(stype[i]!=0)
continue;
if(0 && getd(ble,i) < getd(le,ble) - getd(le,ri) && getd(le,i) == getd(le,ble) + getd(ble,i))
{
stype[i] = 1;
location[i] = location[ble] - getd(ble,i);
}
}
/*
..(..(.......)............).....(..)...
le ri ble
*/
ri = ble;
}
else
{
stype[bri] = 1;
location[bri] = location[ri] - getd(ri,bri);
//assert(getd(ri,bri) > getd(le,ri));
for(int i=0;i<N;i++)
{
if(stype[i]!=0)
continue;
if(0 && getd(bri,i) < getd(ri,bri) - getd(le,ri) && getd(ri,i) == getd(ri,bri) + getd(bri,i))
{
stype[i] = 2;
location[i] = location[bri] + getd(bri,i);
}
}
le = bri;
}
}
//cerr<<"location: ";for(int i=0;i<N;i++) cerr<<location[i]<<" ";cerr<<"\n";
//cerr<<"stype: ";for(int i=0;i<N;i++) cerr<<stype[i]<<" ";cerr<<"\n";
}
/*
..(..(.......)............).)...
le ri ble
*/
