#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
void findLocation(int N, int first, int location[], int stype[]){
location[0] = first;
stype[0] = 1;
if (N == 1) return;
vector<int> d1(N, 0), d2(N, 0);
int csf = pow(10, 7), cs;
for (int i=1; i<N; i++){
d1[i] = getDistance(0, i);
if (d1[i] < csf){
csf = d1[i];
cs = i;
}
}
location[cs] = first+d1[cs];
stype[cs] = 2;
vector<pair<int,int>> l, r;
for (int i=1; i<N; i++){
if (i == cs) continue;
d2[i] = getDistance(cs, i);
if (d2[i] > d1[i]) r.push_back({d1[i], i});
else l.push_back({d2[i], i});
}
int lm = 0, rm = cs;
vector<pair<int,int>> ls, rs;
sort(l.begin(), l.end());
sort(r.begin(), r.end());
for (auto [d, i] : l){
vector<int> pl;
for (auto [j, mx] : ls){
if (d-d2[j] < mx) pl.push_back(location[j]+d-d2[j]);
}
int res = getDistance(lm, i);
bool b = true;
for (int x : pl){
if (x == location[lm]+res){
location[i] = x;
stype[i] = 2;
b = false;
break;
}
}
if (b){
location[i] = location[cs]-d;
stype[i] = 1;
ls.push_back({i, location[lm]-location[i]});
lm = i;
}
}
for (auto [d, i] : r){
vector<int> pl;
for (auto [j, mx] : rs){
if (d-d1[j] < mx) pl.push_back(location[j]-(d-d1[j]));
}
int res = getDistance(rm, i);
bool b = true;
for (int x : pl){
if (x == location[rm]-res){
location[i] = x;
stype[i] = 1;
b = false;
break;
}
}
if (b){
location[i] = location[0]+d;
stype[i] = 2;
rs.push_back({i, location[i]-location[rm]});
rm = i;
}
}
//cout << endl;
//for (int i=0; i<N; i++) cout << stype[i] << " " << location[i] << endl;
return;
}
