#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void findLocation(int N, int first, int location[], int stype[])
{
location[0] = first;
stype[0] = 1;
vector<int> dists(N);
for (int i = 1; i < N; i++) {
dists[i] = getDistance(0, i);
}
int closest = 1;
for (int i = 2; i < N; i++) {
if (dists[i] < dists[closest]) {
closest = i;
}
}
location[closest] = first + dists[closest];
stype[closest] = 2;
vector<int> dists2(N);
vector<pair<int, int>> left, right;
for (int i = 1; i < N; i++) if (i != closest) {
dists2[i] = getDistance(closest, i);
if (dists2[i] + dists[closest] == dists[i]) {
left.emplace_back(dists2[i], i);
} else {
right.emplace_back(dists[i], i);
}
}
sort(left.begin(), left.end());
if (!left.empty()) {
auto [_, top] = left[0];
location[top] = location[closest] - _;
stype[top] = 1;
set<int> up;
up.insert(location[top]);
for (auto [d, i] : left) {
if (i == top) continue;
int ndist = getDistance(top, i);
int x = location[top] + ndist;
int turnpos = *prev(up.upper_bound(x));
int turndist = location[closest] - turnpos + x - turnpos;
if (turndist == d) {
location[i] = x;
stype[i] = 2;
} else {
location[i] = location[closest] - d;
stype[i] = 1;
up.insert(location[i]);
top = i;
}
}
}
sort(right.begin(), right.end());
if (!right.empty()) {
auto [_, btm] = right[0];
location[btm] = location[0] + _;
stype[btm] = 2;
set<int> down;
down.insert(location[btm]);
for (auto [d, i] : right) {
if (i == btm) continue;
int ndist = getDistance(btm, i);
int x = location[btm] - ndist;
int turnpos = *down.upper_bound(x);
int turndist = turnpos - location[0] + turnpos - x;
if (turndist == d) {
location[i] = x;
stype[i] = 1;
} else {
location[i] = location[0] + d;
stype[i] = 2;
down.insert(location[i]);
btm = i;
}
}
}
for (int i = 0; i < N; i++) {
cout << location[i] << " \n"[i == N - 1];
}
for (int i = 0; i < N; i++) {
cout << stype[i] << " \n"[i == N - 1];
}
}
#ifdef EPIC
#include "grader.cpp"
#endif
