#include "rail.h"
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cerr << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
/*
1
4
1 1
2 4
2 7
2 9
2
6
1 3
2 6
2 7
1 1
1 0
2 8
*/
const int INF=1e9;
int gd(int i,int j)
{
return getDistance(i,j);
}
void findLocation(int N, int first, int location[], int stype[])
{
location[0]=first,stype[0]=1;
set<int> loc[3];
if(N==1) return;
vector<int> d0(N,0),d1(N,0),vR,vL;
deque<pii> vis;
for(int i=1;i<N;++i)
d0[i]=gd(0,i),vis.pb(MP(d0[i],i));
sort(ALL(vis));
int x=vis[0].S,tpR,tpL;
vis.pop_front(),location[x]=d0[x]+first,stype[x]=2;
for(int i=1;i<N;++i)
if(i!=x)
d1[i]=gd(i,x);
while(!vis.empty())
{
auto tmp=vis[0].S;
vis.pop_front();
if(d0[tmp]-d1[tmp]==d0[x])
if(d1[tmp]<=d0[x])
location[tmp]=location[x]-d1[tmp],stype[tmp]=1;
else
if(vL.empty())
location[tmp]=first+2*d0[x]-d0[tmp],stype[tmp]=1,vL.pb(location[tmp]),tpL=tmp;
else
{
int dis=gd(tpL,tmp),delta=location[tpL]+(d0[tpL]+dis-d0[tmp])/2;
int p=*lower_bound(vL.rbegin(),vL.rend(),delta);
if(p!=delta)
location[tmp]=first+2*d0[x]-d0[tmp],stype[tmp]=1,vL.pb(location[tmp]),tpL=tmp;
else
location[tmp]=location[tpL]+dis,stype[tmp]=2;
}
else
if(vR.empty())
location[tmp]=d0[tmp]+first,stype[tmp]=2,vR.pb(location[tmp]),tpR=tmp;
else
{
int dis=gd(tpR,tmp),delta=location[tpR]-(d0[tpR]+dis-d0[tmp])/2;
int p=*lower_bound(ALL(vR),delta);
if(p!=delta)
location[tmp]=d0[tmp]+first,stype[tmp]=2,vR.pb(location[tmp]),tpR=tmp;
else
location[tmp]=location[tpR]-dis,stype[tmp]=1;
}
}
}
