#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;
map<pii,int> mp;
pii ans[mxn];
int Ask(int a,int b){
if(mp.find(pii(a,b)) == mp.end())return mp[pii(a,b)] = mp[pii(b,a)] = getDistance(a,b);
else return mp[pii(a,b)];
}
void Answer(int id,int pos,int tp){
cerr<<"ANS: "<<id<<','<<pos<<','<<tp<<endl;
if(ans[id].sc)cerr<<"REPEATED ANSWER: "<<id<<endl;
assert(!ans[id].sc);
ans[id] = pii(pos,tp);
}
int d1[mxn],d2[mxn];
void findLocation(int N, int ori, int location[], int stype[]){
if(N == 1){
location[0] = ori;
stype[0] = 1;
return;
}
vector<pii> da;
for(int i = 0;i<N;i++)d1[i] = Ask(0,i);
int a = 0,b = min_element(d1+1,d1+N)-d1;
cerr<<"[a,b]: "<<a<<','<<b<<endl;
Answer(b,ori+d1[b],2);
cerr<<"INIT DONE!"<<endl;
assert(a != b);
vector<int> vl,vr;
for(int i = 0;i<N;i++)d2[i] = Ask(b,i);
int c = a;
for(int i = 0;i<N;i++)if(i != b&&d2[i]<d2[c])c = i;
for(int i = 0;i<N;i++){
if(i == a||i == b)continue;
int tmp = Ask(a,i)-Ask(b,i)+Ask(b,c);
cerr<<i<<":"<<tmp<<endl;
if(tmp == Ask(a,b)-Ask(b,c)||tmp == 0){
cerr<<"VR: "<<i<<endl;
vr.push_back(i);
}
else{
cerr<<"VL: "<<i<<endl;
vl.push_back(i);
}
}
vl.push_back(a);
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]<d1[b];});
/*
{
for(auto &i:vl)Answer(i,ans[b].fs-Ask(b,i),1);
for(auto &i:vr)Answer(i,ans[a].fs+Ask(a,i),2);
for(int i = 0;i<N;i++){
if(!ans[i].sc)cerr<<"MISS ANS: "<<i<<endl;
assert(ans[i].sc);
location[i] = ans[i].fs;
stype[i] = ans[i].sc;
}
assert(ans[a].fs == ori&&ans[a].sc == 1);
return;
}
*/
int lp = vl[0];
vector<pii> pil;
Answer(lp,ans[b].fs-Ask(b,lp),1);
pil.push_back(pii(lp,ans[lp].fs));
for(int i = 1;i<vl.size();i++){
int now = vl[i];
int d = Ask(lp,now);
int isr = ans[lp].fs+d;
int id = pil[0].fs;
for(auto it = pil.rbegin();it != pil.rend();it++){
if(it->sc<=isr)id = it->fs;
}
bool dir = 0;//dir = 0:left/1:right
cerr<<now<<"::"<<isr<<' '<<id<<' '<<ans[id].fs<<' '<<Ask(b,now)<<endl;
if(ans[id].fs >= isr||ans[b].fs<=isr)dir = 0;
else if(isr-ans[id].fs+Ask(b,id) == Ask(b,now))dir = 1;
else dir = 0;
if(!dir){
Answer(now,ans[b].fs-Ask(b,now),1);
pil.push_back(pii(now,ans[now].fs));
}
else{
Answer(now,isr,2);
}
lp = pil.back().fs;
}
cerr<<"LEFT DONE!"<<endl;
pil.clear();
assert(ans[a].sc);
int rp = b;
pil.push_back(pii(rp,ans[rp].fs));
assert(vr.empty()||vr[0] != b);
for(auto &now:vr){
int d = Ask(rp,now);
int isl = ans[rp].fs-d;
int id = pil[0].fs;
for(auto it = pil.rbegin();it != pil.rend();it++){
if(it->sc>=isl)id = it->fs;
}
bool dir = 0;//dir = 0:out/1:in
cerr<<now<<"::"<<id<<':'<<ans[id].fs<<','<<isl<<' '<<endl;
if(ans[id].fs<=isl||isl<=ans[a].fs)dir = 0;
else if(ans[id].fs-isl+Ask(a,id) == Ask(a,now))dir = 1;
else dir = 0;
if(!dir){
Answer(now,ans[a].fs+Ask(a,now),2);
pil.push_back(pii(now,ans[now].fs));
}
else{
Answer(now,isl,1);
}
rp = pil.back().fs;
}
for(int i = 0;i<N;i++){
if(!ans[i].sc)cerr<<"MISS ANS: "<<i<<endl;
assert(ans[i].sc);
location[i] = ans[i].fs;
stype[i] = ans[i].sc;
}
return;
}
