#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(a,ori,1);
Answer(b,ori+d1[b],2);
for(int i = 0;i<N;i++){
if(i == a||i == b)continue;
if(Ask(a,i)<Ask(b,i)){
Answer(i,ans[a].fs+Ask(a,i),2);
}
else{
Answer(i,ans[b].fs-Ask(b,i),1);
}
}
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;
}
*/
Answer(b,ori+d1[b],2);
cerr<<"INIT DONE!"<<endl;
assert(a != b);
vector<int> vl,vr;
for(int i = 0;i<N;i++){
if(i == a||i == b)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<<','<<d1[i]<<' '<<d2[i]<<endl;
else cerr<<"VR add: "<<i<<','<<d1[i]<<' '<<d2[i]<<endl;
}
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];
Answer(lp,ans[b].fs-Ask(b,lp),1);
for(int i = 1;i<vl.size();i++){
int now = vl[i];
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);
}
}
cerr<<"LEFT DONE!"<<endl;
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++){
if(!ans[i].sc)cerr<<"MISS ANS: "<<i<<endl;
assert(ans[i].sc);
location[i] = ans[i].fs;
stype[i] = ans[i].sc;
}
return;
}
