#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
bitset<1<<20>isthereaD,isthereaC;
int LOC[5010],TYPE[5010];
void toright(vector<pair<int,int>> v,int F,int loc,int locf){
sort(v.begin(),v.end());
int y=F,dy=abs(loc-locf),locy=locf;
isthereaD[locf]=1;
for(auto [k0,i]:v) {
int YY=getDistance(y,i);
int delta=dy+YY-k0;
delta/=2;
if(isthereaD[locy-delta]){
TYPE[i]=1;
LOC[i]=locy-YY;
} else {
TYPE[i]=2;
LOC[i]=loc+k0;
locy=LOC[i];
dy=k0,y=i;
isthereaD[LOC[i]]=1;
}
}
}
void toleft(vector<pair<int,int>> v,int F,int loc,int locf){
sort(v.begin(),v.end());
isthereaC[locf]=1;
int y=F,dy=abs(loc-locf),locy=locf;
for(auto[k0,i]:v){
int YY=getDistance(y,i);
int delta=dy+YY-k0;
delta/=2;
if(isthereaC[locy+delta]){
TYPE[i]=2;
LOC[i]=loc-dy+YY;
} else {
TYPE[i]=1;
LOC[i]=loc-k0;
locy=LOC[i];
dy=k0,y=i;
isthereaC[LOC[i]]=1;
}
}
}
void findLocation(int N, int first, int location[], int stype[]) {
TYPE[0]=1,LOC[0]=first;
vector<pair<int,int>> distto0;
for(int i=1;i<N;i++)
distto0.push_back({getDistance(i,0),i});
sort(distto0.begin(),distto0.end());
auto[L,X]=distto0[0];
LOC[X]=first+L;
TYPE[X]=2;
vector<pair<int,int>>onright,onleft;
for(int uwu=1;uwu<N-1;uwu++){
auto [k0,i]=distto0[uwu];
int kx=getDistance(i,X);
if(L+kx==k0)
onleft.push_back({kx,i});
else onright.push_back({k0,i});
}
toright(onright,X,first,LOC[X]);
toleft(onleft,0,LOC[X],first);
for(int i=0;i<N;i++)
location[i]=LOC[i],stype[i]=TYPE[i];
}
