#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using Vec = vector<T>;
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define ALL(x) begin(x), end(x)
#define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
template <typename T>
bool chmin(T &x, const T &y) {
if (x > y) {
x = y;
return true;
} else {
return false;
}
}
template <typename T>
bool chmax(T &x, const T &y) {
if (x < y) {
x = y;
return true;
} else {
return false;
}
}
constexpr i32 INF = 1001001001;
constexpr i64 INF64 = 3003003003003003003;
void findLocation(int n, int first, int location[], int stype[]) {
Vec<i32> dist_0(n, 0);
REP(i, 1, n) {
dist_0[i] = getDistance(0, i);
}
i32 y = 0;
{
i32 mn = INF;
REP(i, 1, n) {
if (chmin(mn, dist_0[i])) {
y = i;
}
}
}
Vec<i32> dist_y(n, 0);
dist_y[0] = dist_0[y];
REP(i, 1, n) {
if (i != y) {
dist_y[i] = getDistance(i, y);
}
}
stype[0] = 1;
location[0] = first;
stype[y] = 2;
location[y] = first + dist_0[y];
{
Vec<i32> idx;
REP(i, n) {
if (i == 0 || (i != y && dist_y[i] + dist_0[y] == dist_0[i])) {
idx.push_back(i);
}
}
sort(ALL(idx), [&](i32 i, i32 j) -> bool {
return dist_y[i] < dist_y[j];
});
i32 last = -1;
bool seen_0 = false;
Vec<i32> ones;
for (i32 i : idx) {
if (!seen_0) {
location[i] = location[y] - dist_y[i];
stype[i] = 1;
last = i;
ones.push_back(location[i]);
if (i == 0) {
seen_0 = true;
}
continue;
}
i32 d = getDistance(i, last);
i32 ph = location[last] + d;
if (ph >= location[0]) {
location[i] = location[y] - dist_y[i];
stype[i] = 1;
last = i;
ones.push_back(location[i]);
continue;
}
i32 mx = -INF;
for (i32 pos : ones) {
if (pos < ph) {
chmax(mx, pos);
}
}
if (ph - mx + location[y] - mx == dist_y[i]) {
location[i] = ph;
stype[i] = 2;
} else {
location[i] = location[y] - dist_y[i];
stype[i] = 1;
last = i;
ones.push_back(location[i]);
}
}
}
{
Vec<i32> idx;
REP(i, n) {
if (i != 0 && i != y && dist_y[i] + dist_y[0] != dist_0[i]) {
idx.push_back(i);
}
}
sort(ALL(idx), [&](i32 i, i32 j) -> bool {
return dist_0[i] < dist_0[j];
});
i32 last = y;
Vec<i32> twos;
for (i32 i : idx) {
if (last == y) {
location[i] = location[0] + dist_0[i];
stype[i] = 2;
last = i;
twos.push_back(location[i]);
continue;
}
i32 d = getDistance(i, last);
i32 ph = location[last] - d;
if (ph <= location[y]) {
location[i] = location[0] + dist_0[i];
stype[i] = 2;
last = i;
twos.push_back(location[i]);
continue;
}
i32 mn = INF;
for (i32 pos : twos) {
if (pos > ph) {
chmin(mn, pos);
}
}
if (mn - ph + mn - location[0] == dist_0[i]) {
location[i] = ph;
stype[i] = 1;
} else {
location[i] = location[0] + dist_0[i];
stype[i] = 2;
last = i;
twos.push_back(location[i]);
}
}
}
/*i32 x = 0;
{
i32 mn = INF;
REP(i, 0, n) {
if (i != y && chmin(mn, dist_y[i])) {
x = i;
}
}
}
Vec<i32> dist_x(n, 0);
REP(i, n) {
if (i != x) {
dist_x[i] = getDistance(i, x);
}
}
location[y] = first + dist_0[y];
stype[y] = 2;
location[x] = location[y] - dist_y[x];
stype[x] = 1;
{
Vec<i32> idx;
REP(i, n) {
if (i != x && i != y && dist_x[i] > dist_y[i]) {
idx.push_back(i);
}
}
sort(ALL(idx), [&](i32 i, i32 j) -> bool {
return dist_y[i] < dist_y[j];
});
i32 last = x;
Vec<i32> ones;
for (i32 i : idx) {
if (last == x) {
location[i] = location[y] - dist_y[i];
stype[i] = 1;
last = i;
ones.push_back(location[i]);
continue;
}
i32 d = getDistance(i, last);
i32 ph = location[last] + d;
if (ph >= location[x]) {
location[i] = location[y] - dist_y[i];
stype[i] = 1;
last = i;
ones.push_back(location[i]);
continue;
}
i32 mx = -INF;
for (i32 pos : ones) {
if (pos < ph) {
chmax(mx, pos);
}
}
if (ph - mx + location[y] - mx == dist_y[i]) {
location[i] = ph;
stype[i] = 2;
} else {
location[i] = location[y] - dist_y[i];
stype[i] = 1;
last = i;
ones.push_back(location[i]);
}
}
}
{
Vec<i32> idx;
REP(i, n) {
if (i != x && i != y && dist_x[i] < dist_y[i]) {
idx.push_back(i);
}
}
sort(ALL(idx), [&](i32 i, i32 j) -> bool {
return dist_x[i] < dist_x[j];
});
i32 last = y;
Vec<i32> twos;
for (i32 i : idx) {
if (last == y) {
location[i] = location[x] + dist_x[i];
stype[i] = 2;
last = i;
twos.push_back(location[i]);
continue;
}
i32 d = getDistance(i, last);
i32 ph = location[last] - d;
if (ph <= location[y]) {
location[i] = location[x] + dist_x[i];
stype[i] = 2;
last = i;
twos.push_back(location[i]);
continue;
}
i32 mn = INF;
for (i32 pos : twos) {
if (pos > ph) {
chmin(mn, pos);
}
}
if (mn - ph + mn - location[x] == dist_x[i]) {
location[i] = ph;
stype[i] = 1;
} else {
location[i] = location[x] + dist_x[i];
stype[i] = 2;
last = i;
twos.push_back(location[i]);
}
}
}*/
}
