#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> d0, dx;
void findLocation(int N, int first, int location[], int stype[]){
location[0] = first;
stype[0] = 1;
if (N == 1) return;
set<pair<int,int>> cs, ds;
set<int> cls, dls;
cs.insert({first, 0});
cls.insert(first);
d0.resize(N);
d0[0] = 0;
for (int i=1; i<N; i++) d0[i] = getDistance(0, i);
pair<int,int> cl = {pow(10, 7), -1};
for (int i=1; i<N; i++) cl = min(cl, {d0[i], i});
int x = cl.second;
dx.resize(N);
dx[x] = 0;
dx[0] = d0[x];
location[x] = first+d0[x];
stype[x] = 2;
ds.insert({-location[x], x});
dls.insert(location[x]);
vector<int> l, m, r;
for (int i=1; i<N; i++){
if (i == x) continue;
dx[i] = getDistance(x, i);
if (dx[i] < d0[x]) m.push_back(i);
else if (d0[i] == d0[x]+dx[i]) l.push_back(i);
else r.push_back(i);
}
for (int i : m){
location[i] = location[x]-dx[i];
stype[i] = 1;
cs.insert({location[i], i});
cls.insert(location[i]);
}
sort(l.begin(), l.end(), [](int a, int b){return d0[a] < d0[b];});
for (int i : l){
auto [yl, y] = *cs.begin();
int dy = getDistance(y, i);
int z = dx[i]-dx[y]-dy;
z = -z;
int pl = yl+z/2+dx[i]-(location[x]-(yl+z/2));
if (cls.find(yl+z/2) != cls.end()){
location[i] = pl;
stype[i] = 2;
ds.insert({-location[i], i});
dls.insert(location[i]);
}
else {
location[i] = location[x]-dx[i];
stype[i] = 1;
cs.insert({location[i], i});
cls.insert(location[i]);
}
}
sort(r.begin(), r.end(), [](int a, int b){return d0[a] < d0[b];});
for (int i : r){
auto [yl, y] = *ds.begin();
yl = -yl;
int dy = getDistance(y, i);
int z = d0[i]-d0[y]-dy;
z = -z;
int pl = yl-z/2-(d0[i]-((yl-z/2)-location[0]));
if (dls.find(yl-z/2) != dls.end()){
location[i] = pl;
stype[i] = 1;
cs.insert({location[i], i});
cls.insert(location[i]);
}
else {
location[i] = location[0]+d0[i];
stype[i] = 2;
ds.insert({-location[i], i});
dls.insert(location[i]);
}
}
/*cout << endl;
for (int i=0; i<N; i++){
cout << stype[i] << " " << location[i] << endl;
}*/
}
