#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
int n;
typedef pair<int,int> P;
typedef pair<P,int> Pi;
bool vis[5000];
void findLocation(int N, int first, int location[], int stype[]) {
n=N;
priority_queue<Pi,vector<Pi>,greater<Pi>> pq;
location[0]=first;
stype[0]=1;
for(int i=1;i<N;i++) {
int got=getDistance(0,i);
pq.push(Pi(P(got,first+got),-i));
}
vis[0]=true;
while (!pq.empty()) {
Pi now=pq.top();
pq.pop();
int type=1;
if (now.second<0) {
type=2;
now.second=-now.second;
}
if (vis[now.second]) {
continue;
}
vis[now.second]=true;
stype[now.second]=type;
location[now.second]=now.first.second;
for(int i=0;i<n;i++) {
if (vis[i]) {
continue;
}
int got=getDistance(now.second,i);
pq.push(Pi(P(got,location[now.second]+got*(type==1?1:-1)),now.second*(type==1?-1:1)));
}
}
}
