#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());
if (!a.empty()) lst=a[0].second, stype[lst]=2, location[lst]=first+a[0].first;
for (int i=1; i<a.size(); i++)
{
if (query(lst, a[i].second)+query(0, lst)==query(0, a[i].second)) location[a[i].second]=location[lst]-query(lst, a[i].second), stype[a[i].second]=1;
else lst=a[i].second, location[lst]=first+query(0, lst), stype[lst]=2;
}
sort(b.begin(), b.end());
if (!b.empty()) lst=b[0].second, stype[lst]=1, location[lst]=location[mn.second]-b[0].first;
for (int i=1; i<b.size(); i++)
{
if (query(lst, b[i].second)+query(mn.second, lst)==query(mn.second, b[i].second)) location[b[i].second]=location[lst]+query(lst, b[i].second), stype[b[i].second]=2;
else lst=b[i].second, location[lst]=location[mn.second]-query(mn.second, lst), stype[lst]=1;
}
//for (int i=0; i<N; i++) cout<<"debug "<<i<<' '<<stype[i]<<' '<<location[i]<<'\n';
}
