#include "rail.h"
#include <bits/stdc++.h>
#define ll long long
#define el cout << endl
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;
const int maxn = 5e3;
const int INF = 1e9;
int dist[maxn + 10][maxn + 10];
ll do_query(int x, int y)
{
if (dist[x][y] != -1)
return dist[x][y];
return dist[x][y] = dist[y][x] = getDistance(x, y);
}
namespace SUBTASK_1
{
void solve(int n, int first, int location[], int type[])
{
for (int i = 0; i < n; i++)
{
if (i == 0)
{
type[i] = 1;
location[i] = first;
continue;
}
location[i] = getDistance(0, i) + first;
type[i] = 2;
}
}
}
namespace SUBTASK_2
{
void solve(int n, int first, int location[], int type[])
{
ii mn = ii(INF, INF);
for (int i = 0; i < n; i++)
{
if (i == 0)
{
location[0] = first;
type[i] = 1;
continue;
}
mn = min(mn, ii(getDistance(0, i), i));
}
// cout << "OUT!", el;
for (int i = 1; i < n; i++)
{
if (i != mn.se && getDistance(0, mn.se) + getDistance(mn.se, i) == getDistance(0, i))
{
type[i] = 1;
location[i] = first + getDistance(0, mn.se) - getDistance(mn.se, i);
}
else
{
type[i] = 2;
location[i] = first + getDistance(0, i);
}
// cout << "OK: " << i << ' ' << location[i] << ' ' << type[i], el;
}
}
}
namespace SUBTASK_3
{
int dist[maxn + 10][maxn + 10];
void solve(int n, int first, int location[], int type[])
{
type[0] = 1;
location[0] = first;
ii mn = ii(INF, INF);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
dist[i][j] = dist[j][i] = getDistance(i, j);
for (int j = 1; j < n; j++)
mn = min(mn, ii(dist[0][j], j));
type[mn.se] = 2;
location[mn.se] = first + dist[0][mn.se];
vector<int> lft, rgt;
for (int j = 1; j < n; j++)
{
if (j == mn.se)
continue;
if (dist[0][mn.se] + dist[mn.se][j] == dist[0][j])
lft.push_back(j);
else
rgt.push_back(j);
}
// cout << mn.se, el;
// cout << "LEFT: ";
// for (int x : lft)
// cout << x << ' ';
// el;
// cout << "RIGHT: ";
// for (int x : rgt)
// cout << x << ' ';
// el;
auto check_lft = [&] (int p)
{
for (int x : lft)
{
if (x == p)
continue;
if (dist[mn.se][x] + dist[x][p] == dist[mn.se][p])
return x;
}
return -1;
};
auto check_rgt = [&] (int p)
{
for (int x : rgt)
{
if (x == p)
continue;
if (dist[0][x] + dist[x][p] == dist[0][p])
return x;
}
return -1;
};
for (int x : lft)
{
int p = check_lft(x);
if (p == -1)
{
type[x] = 1;
location[x] = first + dist[0][mn.se] - dist[mn.se][x];
}
else
{
type[x] = 2;
location[x] = first + dist[0][mn.se] - dist[mn.se][p] + dist[p][x];
}
}
for (int x : rgt)
{
int p = check_rgt(x);
// cout << x << ' ' << p, el;
if (p == -1)
{
type[x] = 2;
location[x] = first + dist[0][x];
}
else
{
type[x] = 1;
location[x] = first + dist[0][p] - dist[p][x];
}
}
}
};
namespace SUBTASK_4
{
void solve(int n, int first, int location[], int type[])
{
memset(dist, -1, sizeof dist);
vector<int> p(n - 1, 0);
set<ii> C, D;
auto in_C = [&] (int x)
{
auto it = C.lower_bound(ii(x, -1));
return it != C.end() && it->fi == x;
};
auto in_D = [&] (int x)
{
auto it = D.lower_bound(ii(x, -1));
return it != D.end() && it->fi == x;
};
iota(p.begin(), p.end(), 1);
sort(p.begin(), p.end(), [&] (int i, int j)
{
return do_query(0, i) < do_query(0, j);
});
// cout << "P: ", el;
// for (int x : p)
// cout << x << ' ' << dist[0][x], el;
type[0] = 1;
location[0] = first;
type[p[0]] = 2;
location[p[0]] = first + do_query(0, p[0]);
C.insert(ii(first, 0));
D.insert(ii(location[p[0]], p[0]));
for (int i = 1; i < p.size(); i++)
{
int LC = C.begin()->se;
int RD = D.rbegin()->se;
int A = do_query(LC, p[i]);
int B = do_query(p[i], RD);
// cout << p[i] << ' ' << A << ' ' << B << ' ' << LC << ' ' << RD, el;
auto get_AB = [&] ()
{
int pos_pi = location[LC] + A;
int pos_C = (pos_pi + location[RD] - B) / 2;
// cout << pos_C, el;
// for (ii pr : C)
// cout << pr.fi << ' ' << pr.se, el;
if (in_C(pos_C) || (!in_D(pos_C) && pos_C > location[0]))
{
location[p[i]] = pos_pi;
type[p[i]] = 2;
D.insert(ii(location[p[i]], p[i]));
return 1;
}
return 0;
};
auto get_C = [&] ()
{
location[p[i]] = location[RD] - B;
type[p[i]] = 1;
C.insert(ii(location[p[i]], p[i]));
};
if (!get_AB())
get_C();
}
}
}
void findLocation(int n, int first, int location[], int stype[])
{
SUBTASK_4::solve(n, first, location, stype);
}
