#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
int N;
int DIST[5000][5000];
//int getDistance(int i, int j)
//{
// cout << i << ' ' << j << '\n';
// int ret;
// cin >> ret;
// return ret;
//}
void findLocation(int n, int location0, int location[], int stype[])
{
N = n;
stype[0] = 1;
location[0] = location0;
vector <pair <int, int>> V, L, R;
for(int i = 1; i < N; i++)
{
DIST[0][i] = DIST[i][0] = getDistance(0, i);
V.push_back({DIST[0][i], i});
}
sort(V.begin(), V.end());
int d = V.begin()->second;
stype[d] = 2;
location[d] = location[0] + V.begin()->first;
for(int i = 1; i < N; i++)
{
if(i == d) continue;
DIST[d][i] = DIST[i][d] = getDistance(d, i);
}
for(int i = 1; i < N; i++)
{
if(i == d) continue;
if(DIST[0][i] == (DIST[0][d] + DIST[d][i])) L.push_back({DIST[d][i], i});
else R.push_back({DIST[0][i], i});
}
if(L.size())
{
sort(L.begin(), L.end());
while(L.begin()->first < DIST[d][0])
{
stype[L.begin()->second] = 1;
location[L.begin()->second] = location[d] - L.begin()->first;
L.erase(L.begin(), L.begin() + 1);
}
}
if(L.size())
{
int prevc = L.begin()->second;
vector <int> C;
C.push_back(prevc);
stype[prevc] = 1;
location[prevc] = location[d] - DIST[d][prevc];
for(int i = 1; i < L.size(); i++)
{
bool flag = false;
for(int prevc : C)
{
if(!DIST[prevc][L[i].second]) DIST[prevc][L[i].second] = DIST[L[i].second][prevc] = getDistance(prevc, L[i].second);
if(DIST[d][L[i].second] == (DIST[d][prevc] + DIST[prevc][L[i].second]))
{
flag = true;
stype[L[i].second] = 2;
location[L[i].second] = location[prevc] + DIST[prevc][L[i].second];
}
}
if(!flag)
{
prevc = L[i].second;
C.push_back(prevc);
stype[prevc] = 1;
location[prevc] = location[d] - DIST[d][prevc];
}
}
}
if(R.size())
{
sort(R.begin(), R.end());
int prevd = R.begin()->second;
vector <int> D;
D.push_back(prevd);
stype[prevd] = 2;
location[prevd] = location[0] + DIST[0][prevd];
for(int i = 1; i < R.size(); i++)
{
bool flag = false;
for(int prevd : D)
{
if(!DIST[prevd][R[i].second]) DIST[prevd][R[i].second] = DIST[R[i].second][prevd] = getDistance(prevd, R[i].second);
if(DIST[0][R[i].second] == (DIST[0][prevd] + DIST[prevd][R[i].second]))
{
flag = true;
stype[R[i].second] = 1;
location[R[i].second] = location[prevd] - DIST[prevd][R[i].second];
}
}
if(!flag)
{
prevd = R[i].second;
D.push_back(prevd);
stype[prevd] = 2;
location[prevd] = location[0] + DIST[0][prevd];
}
}
}
return;
}
//int main()
//{
// int n, location0;
// cin >> n >> location0;
// int location[n], stype[n];
// findLocation(n, location0, location, stype);
// for(int i = 0; i < n; i++) cout << location[i] << " \n"[i == (n - 1)];
// for(int i = 0; i < n; i++) cout << stype[i] << " \n"[i == (n - 1)];
// return 0;
//}
