#include "rail.h"
/*
*/
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define en '\n'
const int N = 5e3 + 100;
const int INTmx = (int)1e9;
int a[N],b[N],n;
bool ban[N];
int sd[N];
bool was[N][N];
int c[N][N];
int get(int x,int y) {
if(was[x][y])return c[x][y];
was[x][y] = 1;
c[x][y] = getDistance(x,y);
return c[x][y];
}
void findLocation(int NN, int first, int location[], int stype[]) {
n = NN;
location[0] = first;
stype[0] = 1;
pii mn = mp(INTmx,0);
int L = 0;
ban[0] = 1;
for(int i = 1;i < n;i++) {
if(ban[i])continue;
mn = min(mn,mp(get(L,i),i));
}
int R = mn.s;
ban[R] = 1;
location[R] = location[L] + get(L,R);
stype[R] = 2;
int kol = 2;
int lastR = location[L],lastL = location[R];
for(int i = 1;i < n;i++) {
if(ban[i])continue;
if(get(L,i) == get(R,i) + get(L,R) && get(R,i) < get(L,R)) {
stype[i] = 1;
location[i] = location[R] - get(R,i);
ban[i] = 1;
lastR = max(lastR,location[i]);
kol++;
}
}
vector <int> exR,exL;
exR.pb(R);
exL.pb(L);
//cout << R << " " << stype[R] << endl;
while(kol < n) {
mn = mp(INTmx,0);
for(int i = 1;i < n;i++) {
if(ban[i])continue;
mn = min(mn,mp(get(exL[0],i),i));
}
int pos = mn.s;
ban[pos] = 1;
//cout << pos << " ? " << get(exL[0],pos) << " === " << get(exR[0],pos) << " - " << lastR - location[exL[0]] << " + " << location[exR[0]] - lastR << en;
if(get(exL[0],pos) - (lastR - location[exL[0]]) + (location[exR[0]] - lastR) == get(exR[0],pos)) {
int val = get(R,pos);
int need = -1;
for(int i = exR.size() - 2;i >= 0;i--) {
if(val < location[R] - location[exR[i]]) {
need = i;
break;
}
}
//cout << val << " " << need << " " << pos << en;
if(need == -1) {
exR.pb(pos);
stype[pos] = 2;
location[pos] = location[exL[0]] + get(exL[0],pos);
kol++;
R = pos;
continue;
}
need++;
if(get(exL[0],pos) == get(exL[0],R) + val - 2 * (location[R] - location[exR[need]])) {
location[pos] = location[R] - val;
stype[pos] = 1;
kol++;
}else {
exR.pb(pos);
kol++;
stype[pos] = 2;
location[pos] = location[exL[0]] + get(exL[0],pos);
R = pos;
}
}else {
int val = get(L,pos);
int need = -1;
for(int i = exL.size() - 2;i >= 0;i--) {
if(val < location[exL[i]] - location[L]) {
need = i;
break;
}
}
if(need == -1) {
exL.pb(pos);
stype[pos] = 1;
location[pos] = location[exR[0]] - get(exR[0],pos);
kol++;
L = pos;
continue;
}
need++;
if(get(exR[0],pos) == get(exR[0],L) + val - 2 * (location[exL[need]] - location[L])) {
location[pos] = location[L] + val;
stype[pos] = 2;
kol++;
}else {
exL.pb(pos);
stype[pos] = 1;
location[pos] = location[exR[0]] - get(exR[0],pos);
kol++;
L = pos;
}
}
//cout << L << " " << R << endl;
}
}
