#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=5e3+5;
int dp[nx][nx], lst;
int query(int i, int j)
{
if (i>j) swap(i, j);
if (dp[i][j]!=0) return dp[i][j];
return dp[i][j]=getDistance(i, j);
}
vector<pair<int, int>> a, b;
void findLocation(int N, int first, int location[], int stype[])
{
location[0]=first;
stype[0]=1;
pair<int, int> mn={INT_MAX, 0};
for (int i=1; i<N; i++) mn=min(mn, {query(0, i), i});
location[mn.second]=first+mn.first;
stype[mn.second]=2;
for (int i=1; i<N; i++)
{
if (i==mn.second) continue;
if (query(0, mn.second)+query(mn.second, i)==query(0, i)) b.push_back({query(mn.second, i), i});
else a.push_back({query(0, i), i});
}
sort(a.begin(), a.end());
for (int i=0; i<a.size(); i++)
{
int loc;
bool can=1;
for (int j=0; j<i; j++) if (query(0, a[j].second)+query(a[j].second, a[i].second)==query(0, a[i].second)) can=0, loc=a[j].second;
if (!can) location[a[i].second]=location[loc]-query(loc, a[i].second), stype[a[i].second]=1;
else location[a[i].second]=first+query(0, a[i].second), stype[a[i].second]=2;
}
sort(b.begin(), b.end());
for (int i=0; i<b.size(); i++)
{
int loc;
bool can=1;
for (int j=0; j<i; j++) if (query(mn.second, b[j].second)+query(b[j].second, b[i].second)==query(mn.second, b[i].second)) can=0, loc=b[j].second;
if (!can) location[b[i].second]=location[loc]+query(loc, b[i].second), stype[b[i].second]=2;
else location[b[i].second]=location[mn.second]-query(mn.second, b[i].second), stype[b[i].second]=1;
}
//for (int i=0; i<N; i++) cout<<"debug "<<i<<' '<<stype[i]<<' '<<location[i]<<'\n';
}
