// ~ Be Name Khoda ~ //
#include "rail.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 5e3 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
int dis[maxn5][maxn5], mn[maxn5];
bool mark[maxn5];
void findLocation(int n, int first, int location[], int stype[])
{
if(n == 1){
location[0] = first;
stype[0] = 1;
return;
}
for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++)
dis[i][j] = dis[j][i] = getDistance(i, j);
for(int i = 0; i < n; i++){
mn[i] = i == n - 1 ? 0 : i + 1;
for(int j = 0; j < n; j++) if(j != i && dis[i][j] < dis[i][mn[i]])
mn[i] = j;
}
int x = mn[0];
int y = mn[x];
location[y] = first + dis[0][x] - dis[x][y];
stype[y] = 1;
location[x] = first + dis[0][x];
stype[x] = 2;
for(int i = 0; i < n; i++)
//cout << i << ' ' << mn[i] << endl;
for(int i = 0; i < n; i++) if(!mark[i] && i == mn[mn[i]]){
int v = mn[i];
//cout << "here " << i << ' ' << v << endl;
mark[i] = mark[v] = true;
int u = i;
if(u != x && u != y){
if(dis[y][i] < dis[x][i]){
if(dis[y][u] > dis[y][v])
swap(u, v);
location[u] = location[y] + dis[u][y];
location[v] = location[u] - dis[u][v];
stype[u] = stype[x];
stype[v] = stype[y];
}
else{
if(dis[x][u] < dis[x][v])
swap(u, v);
location[v] = location[x] - dis[x][v];
location[u] = location[v] + dis[u][v];
stype[u] = stype[x];
stype[v] = stype[y];
}
}
else if(stype[v] == 2)
swap(u, v);
for(int j = 0; j < n; j++) if(!mark[j]){
//cout << "ha? " << j << ' ' << u << ' ' << v << endl;
if(mn[j] == v){
location[j] = location[v] + dis[j][v];
mark[j] = true;
stype[j] = stype[u];
}
if(mn[j] == u){
location[j] = location[u] - dis[j][u];
stype[j] = stype[v];
mark[j] = true;
}
}
}
return;
//for(int i = 0; i < n; i++)
//cout << "* " << location[i] << ' ' << stype[i] << endl;
return;
}
