#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 5050;
int dp[mxn][mxn];
pii ans[mxn];
int Ask(int a,int b){
return dp[a][b] == -1?dp[a][b] = dp[b][a] = getDistance(a,b):dp[a][b];
}
void Answer(int id,int pos,int tp){
cerr<<"ANS: "<<id<<','<<pos<<','<<tp<<endl;
if(ans[id].fs != -1)cerr<<"REPEATED ANSWER: "<<id<<endl;
assert(ans[id].fs == -1);
ans[id] = pii(pos,tp);
}
int d1[mxn],d2[mxn];
void findLocation(int N, int ori, int location[], int stype[]){
memset(dp,-1,sizeof(dp));
for(auto &i:ans)i = pii(-1,-1);
vector<pii> da;
for(int i = 1;i<N;i++){
da.push_back(pii(Ask(0,i),i));
d1[i] = Ask(0,i);
}
sort(da.begin(),da.end());
int a = 0,b = da[0].sc;
cerr<<"[a,b]: "<<a<<','<<b<<endl;
Answer(a,ori,1);
Answer(b,ori+da[0].fs,2);
cerr<<"INIT DONE!"<<endl;
vector<int> vl,vr;
for(int i = 0;i<N;i++){
if(i == b||i == a)continue;
d2[i] = Ask(b,i);
if(d1[i]>d2[i])vl.push_back(i);
else vr.push_back(i);
if(d1[i]>d2[i])cerr<<"VL add: "<<i<<endl;
else cerr<<"VR add: "<<i<<endl;
}
sort(vl.begin(),vl.end(),[](int a,int b){return d2[a]<d2[b];});
sort(vr.begin(),vr.end(),[](int a,int b){return d1[a]<d2[b];});
int lp = a;
for(auto &now:vl){
if(Ask(lp,b)+Ask(lp,now) != Ask(b,now)){
Answer(now,ans[b].fs-Ask(b,now),1);
lp = now;
}
else{
Answer(now,ans[lp].fs+Ask(lp,now),2);
}
}
int rp = b;
for(auto &now:vr){
if(Ask(a,rp)+Ask(rp,now) != Ask(a,now)){
Answer(now,ans[a].fs+Ask(a,now),2);
rp = now;
}
else{
Answer(now,ans[rp].fs-Ask(rp,now),1);
}
}
for(int i = 0;i<N;i++){
assert(ans[i].fs != -1);
location[i] = ans[i].fs;
stype[i] = ans[i].sc;
}
return;
}
