#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)((a).size())
constexpr int maxn = 5010;
bool mark[maxn], lado[maxn];
int dp[maxn][maxn];
int dist(int a, int b) { return dp[a][b] ? dp[a][b] : dp[a][b] = getDistance(a, b); }
void findLocation(int N, int first, int location[], int stype[])
{
int menor = 0, d = 0x3f3f3f3f;
for(int i = 1; i < N; i++)
if(dist(0, i) < d) menor = i, d = dist(0, i);
location[0] = first; stype[0] = 1;
location[menor] = first + d; stype[menor] = 2;
vector<int> l, r;
for(int i = 1; i < N; i++) {
if(i == menor) continue;
if(dist(0, i) == d + dist(menor, i)) l.pb(i);
else r.pb(i), lado[i] = 1;
}
sort(all(l), [](int x, int y) { return dp[0][x] < dp[0][y]; });
sort(all(r), [](int x, int y) { return dp[0][x] < dp[0][y]; });
// printf("%d %d\n", sz(l), sz(r));
for(int i = 0; i < sz(r);) {
location[r[i]] = location[0] + dist(0, r[i]); stype[r[i]] = 2;
// printf("r %d\n", r[i]);
int j = i+1;
for(; dist(0, r[j]) == dist(0, r[i]) + dist(r[i], r[j]) && j < sz(r); j++)
location[r[j]] = location[r[i]] - dist(r[i], r[j]), stype[r[j]] = 1;
i = j;
}
for(int i = 0; i < sz(l);) {
location[l[i]] = location[menor] - dist(menor, l[i]); stype[l[i]] = 1;
// printf("l %d\n", l[i]);
int j = i+1;
for(; dist(menor, l[j]) == dist(menor, l[i]) + dist(l[i], l[j]) && j < sz(l); j++)
location[l[j]] = location[l[i]] - dist(l[i], l[j]), stype[l[j]] = 2;
i = j;
}
// for(int i = 0; i < N; i++)
// printf("%d ", location[i]);
// puts("");
// for(int i = 0; i < N; i++)
// printf("%d ", stype[i]);
// puts("");
}
