#include <bits/stdc++.h>
#include "rail.h"
// mrrrow meeeow nyaa :3c
// play vivid/stasis! it's a really awesome free game on steam
#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define pb push_back
#define pob pop_back
#define p push
#define po pop
#define f first
#define s second
#define ub upper_bound
#define lb lower_bound
#define be(a) a.begin(), a.end()
using namespace std;
int ____init = []
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
return 0;
}();
map<pair<int, int>, int> cache;
int dist(int i, int j)
{
if (i == j)
return 0;
if (i > j)
swap(i, j);
if (cache.count({i, j}))
return cache[{i, j}];
return cache[{i, j}] = getDistance(i, j);
}
void findLocation(int n, int first, int location[], int stype[])
{
vector<int> b;
location[0] = first;
stype[0] = 1;
fo(i, 1, n)
{
location[i] = first + dist(0, i), stype[i] = 2;
b.pb(i);
}
sort(be(b), [&](int &i, int &j)
{ return location[i] < location[j]; });
vector<int> c;
vector<int> d;
for (int i : b)
{
of(j, 0, c.size())
{
if (dist(0, i) == dist(0, c.back()) + dist(c.back(), i) - 2 * (location[c.back()] - location[c[j]]))
{
location[i] = location[c.back()] - dist(c.back(), i);
stype[i] = 1;
if (location[i] < first)
d.pb(i);
goto cont;
}
}
c.pb(i);
cont:;
}
sort(be(d), [&](int &i, int &j)
{ return location[i] > location[j]; });
vector<int> e;
for (int i : d)
{
of(j, 0, e.size())
{
if (dist(0, i) == dist(0, e.back()) + dist(e.back(), i) - 2 * (location[e[j]] - location[e.back()]))
{
location[i] = location[e.back()] + dist(e.back(), i);
stype[i] = 2;
goto cont2;
}
}
e.pb(i);
cont2:;
}
}
