#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
#include "rail.h"
int N, S;
ii closeD() { // closest D, returns {idx, pos}
int x = -1;
int mdist = 1e9; // minimum distance
int xp = -1;
for (int i = 1; i < N; i++) {
int dist = getDistance(0, i);
if (dist < mdist) {
x = i;
xp = S + dist;
mdist = dist;
}
}
return {x, xp};
}
void findLocation(int n, int s, int location[], int stype[]) {
N = n; S = s;
ii pr = closeD();
int xd = pr.fi;
int pd = pr.se;
location[0] = S;
stype[0] = 1;
location[xd] = pd;
stype[xd] = 2;
for (int i = 0; i < N; i++) {
if (i == 0 || i == xd)
continue;
int d1 = getDistance(0, i);
int d2 = getDistance(xd, i);
if (d1 > d2) { // type C
location[i] = pd - d2;
stype[i] = 1;
}
else { // type D
location[i] = S + d1;
stype[i] = 2;
}
}
}
