#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
typedef long long ll;
void findLocation(int n,int _t,int pos[],int tp[])
{
for(int i=0;i<n;i++) pos[i]=-1;
pos[0]=_t;
tp[0]=1;
map<array<int,2>,int> dist;
auto d=[&](int i,int j)->int
{
if(i==j) return 0;
if(dist.find({i,j})!=dist.end()) return dist[{i,j}];
return (dist[{i,j}]=dist[{j,i}]=getDistance(i,j));
};
int x=1;
for(int i=1;i<n;i++) if(d(0,i)<d(0,x)) x=i;
pos[x]=pos[0]+d(0,x);
tp[x]=2;
vector<int> left,right;
for(int i=0;i<n;i++)
{
if(i==0||i==x) continue;
if(d(0,x)+d(x,i)>d(0,i)) right.push_back(i);
else if(d(x,i)<d(x,0))
{
pos[i]=pos[x]-d(x,i);
tp[i]=1;
}
else left.push_back(i);
}
//process right
vector<array<int,2>> dtypes;
dtypes.push_back({pos[x],x});
int r=x;
sort(right.begin(),right.end(),[&](int i,int j){return (d(0,i)<d(0,j));});
for(int i:right)
{
int nl=pos[r]-d(r,i);
int t=(*lower_bound(dtypes.begin(),dtypes.end(),array<int,2>{nl,0}))[1];
if(d(0,t)+pos[t]-nl==d(0,i))
{
pos[i]=nl;
tp[i]=1;
}
else
{
pos[i]=pos[0]+d(0,i);
tp[i]=2;
r=i;
dtypes.push_back({pos[i],i});
}
}
//process left
vector<array<int,2>> ctypes;
ctypes.push_back({-pos[0],0});
int l=0;
sort(left.begin(),left.end(),[&](int i,int j){return (d(x,i)<d(x,j));});
for(int i:left)
{
int nr=pos[l]+d(l,i);
int t=(*lower_bound(ctypes.begin(),ctypes.end(),array<int,2>{-nr,0}))[1];
if(d(x,t)+nr-pos[t]==d(x,i))
{
pos[i]=nr;
tp[i]=2;
}
else
{
pos[i]=pos[x]-d(x,i);
tp[i]=1;
l=i;
ctypes.push_back({-pos[i],i});
}
}
}
