#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second
#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int iinf = 0x3f3f3f3f;
const int maxn = 3e5+5;
int got[5005][5005];
int n;
inline int RV(int x) {
return n-1-x;
}
bool OPP=0;
inline int dis(int a, int b) {
if (OPP) {
a = RV(a); b = RV(b);
}
if (a == b) return 0;
if (got[a][b] == -1) {
got[a][b] = got[b][a] = getDistance(a,b);
}
return got[a][b];
}
void run(vector<int> stuff, int A, int C, int location[], int stype[]) {
vector<int> Ds;
Ds.pb(C);
sort(ALL(stuff), [&](int x, int y) {return dis(A,x) < dis(A,y);});
for (int x : stuff) {
int dstdf = dis(A,Ds.back()) + dis(Ds.back(), x) - dis(A,x);
assert(dstdf % 2 == 0); dstdf /= 2;
bool done = 0;
for (int e : Ds) {
if (location[Ds.back()] - location[e] == dstdf) {
location[x] = location[e] - (dis(A,x) - location[e]);
stype[x] = 1;
bug(x, e, location[x]);
done = 1; break;
}
}
if (!done) {
stype[x] = 2;
location[x] = dis(A,x) + location[A];
bug(x, "D", location[x]);
Ds.pb(x);
}
}
}
void findLocation(int _n, int _first, int location[], int stype[])
{
// add _first at the very end
n = _n;
memset(got, -1, sizeof got);
fill(stype, stype+n, 0);
// DO NOT CALL getDistance
int A = 0, C = -1;
REP(i,n) {
if (i == A) continue;
if (C == -1 || dis(A,i) < dis(A,C)) {
C = i;
}
}
assert(C != -1);
vector<int> L, R; // to the left of A or to the right of C
bug(A,C);
REP(i,n) {
if (i == A) {
location[i] = 0; stype[i] = 1; // 1 is type C
continue;
}
if (i == C) {
location[i] = 0 + dis(A,C); stype[i] = 2; // 2 is type D
continue;
}
if (dis(A,i) == dis(A,C) + dis(C,i)) {
// to the left of C
if (dis(C,i) < dis(A,C)) {
// between A and C
location[i] = location[C] - dis(C,i);
stype[i] = 1;
bug(i, location[i], "btw A and C");
continue;
}else{
L.pb(i);
}
}else{
R.pb(i);
}
}
run(R, A, C, location, stype);
// reversal time (!?)
REP(i,n) {
location[i] = -location[i];
if (stype[i]) stype[i] ^= 3;
}
run(L,C,A,location, stype);
REP(i,n) {
location[i] = -location[i];
if (stype[i]) stype[i] ^= 3;
}
REP(i,n) {
location[i] += _first;
bug(i, stype[i]==1?"C":"D",location[i]);
}
}
