#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> ans(5001);
vector<int> banana(5001);
void calc(vector<pair<int,int>> wut, int c, int p) {
if(wut.empty()) {
return;
}
sort(wut.begin(),wut.end());
set<int> idk;
int z = p+c*wut[0].first,t = wut[0].second;
int w = wut[0].first;
idk.insert(z);
ans[t] = z;
banana[t] = 2;
for(int i = 1; i < wut.size(); i++) {
int v = wut[i].second,d = wut[i].first;
int x = getDistance(t,v);
if((x-d+w)%2 == 0 && idk.find(z-((x-d+w)/2)) == idk.end()) {
ans[v] = p+c*d;
banana[v] = 2;
z = ans[v];
idk.insert(z);
t = v;
w = d;
}
else {
ans[v] = p+c*(w-x);
banana[v] = 1;
}
}
if(c == -1) {
for(int i = 0; i < wut.size(); i++) {
banana[wut[i].second] = 3-banana[wut[i].second];
}
}
}
void findLocation(int N, int p, int location[], int stype[])
{
n = N;
vector<int> haha(n);
vector<int> bruh(n);
vector<bool> troll(n,true);
troll[0] = false;
for(int i = 1; i < n; i++) {
haha[i] = getDistance(0,i);
}
int t,sm = INT_MAX;
for(int i = 1; i < n; i++) {
if(haha[i] < sm) {
sm = haha[i];
t = i;
}
}
troll[t] = false;
location[0] = p;
stype[0] = 1;
location[t] = p+sm;
stype[t] = 2;
for(int i = 1; i < n; i++) {
if(i != t) {
int c = getDistance(t,i);
bruh[i] = c;
if(haha[i] == sm+c) {
stype[i] = 1;
troll[i] = false;
location[i] = location[t]-c;
}
}
}
vector<pair<int,int>> a(0);
vector<pair<int,int>> b(0);
for(int i = 0; i < n; i++) {
if(troll[i]) {
if(haha[i] == bruh[i]+sm) {
a.push_back({bruh[i],i});
}
else {
b.push_back({haha[i],i});
}
}
}
calc(a,-1,p+sm);
calc(b,1,p);
for(int i = 0; i < n; i++) {
if(troll[i]) {
location[i] = ans[i];
stype[i] = banana[i];
}
}
}
