// In the name of Allah
#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6 + 4;
int n, D, v1, v2;
int D1[maxn], D2[maxn];
vector<int> ls1, ls2;
int Dv[maxn]; pii valx[maxn];
pii res[maxn];
int getDistance(int x, int y);
void setx(int i, pii x) {
res[i] = x;
valx[x.F] = Mp(i, x.S);
}
bool cmp(int i, int j) {
return (Dv[i] < Dv[j]);
}
void solvex(int v, vector<int> ls) {
sort(all(ls), cmp);
int vx = -1, R = ((res[v].S == 0) ? 1 : -1);
for (int i : ls) {
if (i == v) continue;
if (vx == -1) {
setx(i, Mp(res[v].F + R * Dv[i], 1 - res[v].S));
vx = i;
continue;
}
int Dx = getDistance(vx, i), w = Dv[vx] + Dx;
if ((w - Dv[i]) % 2 == 1) {
setx(i, Mp(res[v].F + R * Dv[i], 1 - res[v].S));
vx = i;
}
else {
int s = (w - Dv[i]) / 2;
int lc = res[vx].F - R * s;
if (lc >= 0 && lc < maxn && valx[lc].S == 1 - res[v].S) {
setx(i, Mp(res[vx].F - R * Dx, 1 - res[vx].S));
}
else {
setx(i, Mp(res[v].F + R * Dv[i], 1 - res[v].S));
vx = i;
}
}
}
}
void findLocation(int nx, int dx, int location[], int stype[]) {
n = nx; D = dx;
if (n == 1) {
location[0] = D; stype[0] = 1;
return ;
}
v1 = 0, v2 = -1;
for (int i = 0; i < n; i++) {
if (i == v1) D1[i] = 0;
else {
D1[i] = getDistance(v1, i);
if (v2 == -1 || D1[i] < D1[v2]) v2 = i;
}
}
for (int i = 0; i < n; i++) {
if (i == v2) D2[i] = 0;
else if (i == v1) D2[i] = D1[v2];
else D2[i] = getDistance(v2, i);
}
for (int i = 0; i < n; i++) {
if (D1[i] == D1[v2] + D2[i]) ls2.pb(i);
else ls1.pb(i);
}
for (int i = 0; i < n; i++) Dv[i] = D1[i];
fill(valx, valx + maxn, Mp(-1, -1));
setx(v1, Mp(D, 0)); solvex(v1, ls1);
for (int i = 0; i < n; i++) Dv[i] = D2[i];
fill(valx, valx + maxn, Mp(-1, -1));
setx(v2, Mp(D + D1[v2], 1)); solvex(v2, ls2);
for (int i = 0; i < n; i++) {
location[i] = res[i].F; stype[i] = res[i].S + 1;
}
return ;
}
