#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;
int occupied[1000007];
int d0[5003], d1[5003];
void findLocation(int n, int zeroth, int location[], int type[]){
int len = 2e9, ind = 0;
for(int i = 1; i < n; i++){
d0[i] = getDistance(0, i);
if(d0[i] < len){
len = d0[i];
ind = i;
}
}
location[0] = zeroth;
type[0] = occupied[zeroth] = 1;
location[ind] = zeroth+len;
type[ind] = occupied[zeroth+len] = 2;
for(int i = 0; i < n; i++){
if(ind != i){
d1[i] = getDistance(ind, i);
}
}
vector <pii> left, right;
for(int i = 1; i < n; i++){
if(i != ind){
if(d0[i] == len+d1[i]){
if(len > d1[i]){
location[i] = location[ind]-d1[i];
type[i] = occupied[location[i]] = 1;
}
else{
left.pb(mp(d1[i], i));
}
}
else{
right.pb(mp(d0[i], i));
}
}
}
sort(all(left));
sort(all(right));
int R = ind;
for(auto a : right){
auto x = a.second;
auto drx = getDistance(R, x);
auto gap = (d0[R]+drx-d0[x])/2;
if(occupied[location[R]-gap] == 1 || occupied[location[R]-gap] == 0){
location[x] = d0[x]+zeroth;
type[x] = occupied[location[x]] = 2;
R = x;
}
else{
location[x] = location[R]-drx;
type[x] = occupied[location[x]] = 1;
}
}
R = 0;
for(auto a : left){
auto x = a.second;
auto drx = getDistance(R, x);
auto gap = (d1[R]+drx-d1[x])/2;
if(occupied[location[R]+gap]%2 == 0){
location[x] = location[ind]-d1[x];
type[x] = occupied[location[x]] = 1;
R = x;
}
else{
location[x] = location[R]+drx;
type[x] = occupied[location[x]] = 2;
}
}
}
/*
4
6
1 4
2 5
2 10
1 1
1 0
2 2
*/
