#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define F first
#define S second
// typedef struct Station {
// int index;
// int type;
// int location;
// int L,R;
// }STATION;
// long long cnt;
// static int S,SUBTASK;
// static STATION stations[10004];
//
// int cmp_fun_1(const void *a,const void *b)
// {
// STATION c,d;
// c = *(STATION*)(a);
// d = *(STATION*)(b);
// return c.location < d.location ? -1 : 1;
// }
//
// int cmp_fun_2(const void *a,const void *b)
// {
// STATION c,d;
// c = *(STATION*)(a);
// d = *(STATION*)(b);
// return c.index < d.index ? -1 : 1;
// }
//
// void now_I_want_to_getLR(){
// int now = stations[S-1].index,i;
// for(i=S-2;i>=0;i--){
// stations[i].R = now;
// if(stations[i].type==2) now = stations[i].index;
// }
// now = stations[0].index;
// for(i=1;i<S;i++){
// stations[i].L = now;
// if(stations[i].type==1) now = stations[i].index;
// }
// }
//
// int getDistance(int x,int y)
// {
// cnt++;
// if(x==y) return 0;
// if(x<0 || x>=S || y<0 || y>=S) return -1;
// if(stations[x].location > stations[y].location){
// int tmp = x;
// x = y;
// y = tmp;
// }
// int ret = 0;
// if(stations[x].type==1 && stations[y].type==1){
// ret = stations[stations[y].R].location-stations[x].location+stations[stations[y].R].location-stations[y].location;
// }else if(stations[x].type==1 && stations[y].type==2){
// ret = stations[y].location-stations[x].location;
// }else if(stations[x].type==2 && stations[y].type==2){
// ret = stations[x].location-stations[stations[x].L].location+stations[y].location-stations[stations[x].L].location;
// }else if(stations[x].type==2 && stations[y].type==1){
// ret = stations[x].location-stations[stations[x].L].location+stations[stations[y].R].location
// -stations[stations[x].L].location+stations[stations[y].R].location-stations[y].location;
// }
// return ret;
// }
//
//
// void getInput()
// {
// int g;
// g = scanf("%d",&SUBTASK);
// g = scanf("%d",&S);
// int s;
// for (s = 0; s < S; s++) {
// int type, location;
// g = scanf(" %d %d",&type,&location);
// stations[s].index = s;
// stations[s].location = location;
// stations[s].type = type;
// stations[s].L = -1;
// stations[s].R = -1;
// }
// qsort(stations, S, sizeof(STATION), cmp_fun_1);
// now_I_want_to_getLR();
// qsort(stations, S, sizeof(STATION), cmp_fun_2);
// }
//
// int serverGetStationNumber()
// {
// return S;
// }
//
// int serverGetSubtaskNumber()
// {
// return SUBTASK;
// }
//
// int serverGetFirstStationLocation()
// {
// return stations[0].location;
// }
int n;
int dist[5050][5050];
int nw_c,nw_d,base_c,base_d;
bool done[5050];
vector<int> l,r;
vector<pair<int,int> > vec[5050];
int fi_dis(int a,int b)
{
if(a==b)return 0;
if(dist[a][b])return dist[a][b];
return dist[a][b]=dist[b][a]=getDistance(a,b);
}
void findLocation(int N, int first, int location[], int stype[])
{
// memset(dist,0,sizeof(dist));
// memset(done,0,sizeof(done));
// l.clear();
// r.clear();
// for(int i=0;i<5050;i++)
// vec[i].clear();
n=N;
nw_c=0;
location[0]=first;
stype[0]=1;
done[0]=true;
if(n==1)return ;
vec[0].clear();
for(int i=1;i<n;i++)
vec[0].PB({fi_dis(0,i),i});
sort(vec[0].begin(),vec[0].end());
nw_d=vec[nw_c][0].S;
location[nw_d]=location[nw_c]+vec[nw_c][0].F;
stype[nw_d]=2;
done[nw_d]=true;
if(n==2)return ;
vec[nw_d].clear();
for(int i=0;i<n;i++)
{
if(i==nw_d)continue;
vec[nw_d].PB({fi_dis(nw_d,i),i});
// printf("dis: %d %d: %d\n",nw_d,i,getDistance(nw_d,i));
}
sort(vec[nw_d].begin(),vec[nw_d].end());
base_d=nw_d;
base_c=vec[nw_d][0].S;
// printf("base: %d %d\n",base_c,base_d);
// for(auto val:vec[nw_d])
// printf("%d %d\n",val.F,val.S);
nw_c=vec[nw_d][0].S;
location[nw_c]=location[nw_d]-vec[nw_d][0].F;
stype[nw_c]=1;
done[nw_c]=true;
vec[base_c].clear();
for(int i=0;i<n;i++)
{
int a=base_c,b=i;
if(a==b)continue;
dist[a][b]=dist[b][a]=dist[0][i]-(location[a]-location[0]);
// printf("i %d\n",i);
vec[a].PB({dist[a][b],i});
}
sort(vec[base_c].begin(),vec[base_c].end());
for(int i=0;i<vec[base_c].size();i++)
{
int go=vec[base_c][i].S;
if(done[go])continue;
// printf("go %d\n",go);
if(dist[base_c][go]<dist[base_d][go]) r.PB(go);
else l.PB(go);
}
nw_c=base_c;
nw_d=base_d;
for(int i=0;i<r.size();i++)
{
int go=r[i];
int nw_c_go=dist[base_c][go]-(location[nw_c]-location[base_c]);
int nw_d_go=fi_dis(nw_d,go);
// printf("%d\n",go);
done[go]=true;
if(nw_c_go<nw_d_go)
{
// type d
location[go]=location[nw_c]+nw_c_go;
stype[go]=2;
nw_d=go;
}
else
{
// type c
location[go]=location[nw_d]-nw_d_go;
stype[go]=1;
if(location[nw_c]<location[go])
nw_c=go;
}
}
nw_c=base_c;
nw_d=base_d;
for(int i=0;i<l.size();i++)
{
int go=l[i];
int nw_c_go=fi_dis(nw_c,go);
int nw_d_go=dist[base_d][go]-(location[base_d]-location[nw_d]);
// printf("%d\n",go);
done[go]=true;
if(nw_d_go<nw_c_go)
{
// type c
location[go]=location[nw_d]-nw_d_go;
stype[go]=1;
nw_c=go;
}
else
{
// type d
location[go]=location[nw_c]+nw_c_go;
stype[go]=2;
if(location[go]<location[nw_d])
nw_d=go;
}
}
// for(int i=0;i<n;i++)
// {
// printf("%d %d\n",location[i],stype[i]);
// }
return ;
}
// int main()
// {
// int i;
// getInput();
// cnt = 0;
//
// int location[10005];
// int type[10005];
// int ok = 1;
// findLocation(S, serverGetFirstStationLocation(),location, type);
// if(SUBTASK==3 && cnt>S*(S-1)) ok = 0;
// if(SUBTASK==4 && cnt>3*(S-1)) ok = 0;
//
//
// for (i = 0; i < S; i++)
// if(type[i]!=stations[i].type || location[i]!=stations[i].location)
// ok = 0;
// if(ok==0) printf("Incorrect");
// else printf("Correct");
// return 0;
// }
