#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<double, double> pd;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;
const int MAX_N = 5e3 + 100, MAX_M = 1e6 + 100;
int N, Fi, Se, Dix, Lo[MAX_N], Type[MAX_M];
int D[2][MAX_N];
void record(int ix, int lo, int ty) {
Lo[ix] = lo;
Type[lo] = ty;
}
void recordAuto(int fr, int to, int d) {
if(Type[Lo[fr]] == 1) record(to, Lo[fr] + d, 2);
else record(to, Lo[fr] - d, 1);
}
void findLocation(int n, int fi, int location[], int stype[]) {
N = n; Fi = fi;
record(0, fi, 1);
int fminV = INF;
for(int i=0; i<N; i++) {
if(i == 0) continue;
D[0][i] = getDistance(0, i);
if(fminV > D[0][i]) {
fminV = D[0][i];
Dix = i;
}
}
Se = Fi + fminV;
recordAuto(0, Dix, fminV);
vector<int> ls, rs;
for(int i=0; i<N; i++) {
if(i == 0 || i == Dix) continue;
D[1][i] = getDistance(Dix, i);
if(D[0][i] == D[1][i] + D[0][Dix]) {
if(D[1][i] < D[0][Dix]) {
record(i, Lo[Dix] - D[1][i], 1);
}else{
ls.push_back(i);
}
}else rs.push_back(i);
}
sort(ALL(ls), [&](int a, int b) {return D[1][a] < D[1][b];});
sort(ALL(rs), [&](int a, int b) {return D[1][a] < D[1][b];});
int nowC = 0, loC = Fi;
for(int ix : ls) {
int x = Se - D[1][ix];
int d = getDistance(nowC, ix);
int rest = loC - x;
if(Type[loC + (d - rest) / 2] == 1) {
recordAuto(nowC, ix, d);
}else{
recordAuto(Dix, ix, D[1][ix]);
nowC = ix;
loC = Lo[ix];
}
}
int nowD = Dix, loD = Se;
for(int ix : rs) {
int x = Fi + D[0][ix];
int d = getDistance(nowD, ix);
int rest = x - loD;
if(Type[loD - (d - rest) / 2] == 2) {
recordAuto(nowD, ix, d);
}else{
recordAuto(0, ix, D[0][ix]);
nowD = ix;
loD = Lo[ix];
}
}
for(int i=0; i<N; i++) {
location[i] = Lo[i];
stype[i] = Type[Lo[i]];
}
return;
}
