#include "rail.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
//typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
void findLocation(int n, int loc, int location[], int stype[]){
set <pii> Cs, Ds;
vector <pii> v;
int firstD;
location[0] = loc;
stype[0] = 1;
Cs.insert(mp(loc, 0));
for(int i = 1; i < n; i++){
v.pb(mp(getDistance(0, i), i));
}
sort(rall(v));
firstD = v.back().second;
location[firstD] = v.back().first+loc;
stype[firstD] = 2;
Ds.insert(mp(location[firstD], firstD));
v.pop_back();
while(sz(v)){
auto it = v.back();
v.pop_back();
auto ddd = getDistance(firstD, it.second);
if(ddd > it.first){
location[it.second] = it.first+loc;
stype[it.second] = 2;
Ds.insert(mp(location[it.second], it.second));
}
else{
auto assumed_loc = location[firstD]-(it.first-(location[firstD]-loc));
auto to = *Cs.lb(mp(assumed_loc, 0));
ddd = getDistance(to.second, it.second);
if(ddd == to.first-assumed_loc){
location[it.second] = to.first+ddd;
stype[it.second] = 2;
Ds.insert(mp(location[it.second], it.second));
}
else{
location[it.second] = assumed_loc;
stype[it.second] = 1;
Cs.insert(mp(location[it.second], it.second));
}
}
}
}
