#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
// const int maxn = 5005;
// int n;
// int dist[maxn][maxn];
void findLocation(int n, int pos0, int pos[], int type[]) {
pos[0] = pos0, type[0] = 1;
if (n==1) return;
int dist[n][n];
vector<pair<int,int>> v;
for (int i=1;i<n;i++) {
dist[0][i] = getDistance(0, i);
v.push_back({dist[0][i], i});
}
sort(v.begin(), v.end());
vector<pair<int,int>> Df, Cb;
int pos1, s1;
for (auto [d, id]:v) {
if (Df.size() == 0) {
pos1 = pos[id] = pos0 + dist[0][id], type[id] = 2;
s1 = id;
Df = {{pos[id], id}};
continue;
}
int last = Df.back().second;
dist[last][id] = getDistance(last, id);
int curpos = pos[last] - dist[last][id];
int nxt = (*lower_bound(Df.begin(), Df.end(), make_pair(curpos, 0))).second;
if (dist[last][id] - (pos[last]-pos[nxt]) + dist[0][nxt] == dist[0][id]) {
if (curpos < 0) {
dist[s1][id] = dist[0][id] - dist[0][s1];
if (Cb.size() == 0) {
pos[id] = pos1 - dist[s1][id], type[id] = 1;
Cb = {{-pos[id], id}};
continue;
}
int last1 = Cb.back().second;
dist[last1][id] = getDistance(last1, id);
int curpos1 = -pos[last1] - dist[last1][id];
int nxt1 = (*lower_bound(Cb.begin(), Cb.end(), make_pair(curpos, 0))).second;
if (dist[last1][id] - (pos[last1]-pos[nxt1]) + dist[s1][nxt1] == dist[s1][id]) {
pos[id] = -curpos, type[id] = 2;
} else {
pos[id] = pos1 - dist[s1][id], type[id] = 1;
Cb.push_back({-pos[id], id});
}
} else pos[id] = curpos, type[id] = 1;
} else {
pos[id] = pos0 + dist[0][id], type[id] = 2;
Df.push_back({pos[id], id});
}
}
// for (int i=0;i<n;i++) cout << type[i] << " " << pos[i] << endl;
}
