#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
/*
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 my_location[10005],my_stype[10005],my_n;
int inf=1e9;
int d_after(int y)
{
int ret=inf;
for(int i=0;i<my_n;i++)
if(my_stype[i]==2&&my_location[i]>my_location[y])
ret=min(ret,my_location[i]);
return ret;
}
int d_before(int x)
{
int ret=-inf;
for(int i=0;i<my_n;i++)
if(my_stype[i]==1&&my_location[i]<my_location[x])
ret=max(ret,my_location[i]);
return ret;
}
int manual_dist(int x,int y)
{
if(x==y)return 0;
if(my_location[x]>my_location[y])swap(x,y);
if(my_stype[x]==1&&my_stype[y]==2)return my_location[y]-my_location[x];
if(my_stype[x]==1&&my_stype[y]==1)return 2*d_after(y)-my_location[y]-my_location[x];
if(my_stype[x]==2&&my_stype[y]==2)return my_location[x]+my_location[y]-2*d_before(x);
return my_location[x]-2*d_before(x)+2*d_after(y)-my_location[y];
}
void findLocation(int N, int first, int location[], int stype[])
{
my_n=N;
vector< pair<int,int> > d={};
for(int i=1;i<N;i++)
d.push_back({getDistance(0,i),i});
sort(d.begin(),d.end());
my_stype[0]=1;
my_location[d[0].second]=d[0].first;
my_stype[d[0].second]=2;
int most_left=0,most_right=d[0].second;
/*
cout<<"first= "<<first<<endl;
for(int i=0;i<N;i++)cout<<i<<" -> "<<my_location[i]<<" "<<my_stype[i]<<endl;
cout<<"---"<<endl;
*/
for(int i=1;i<d.size();i++)
{
int pos=d[i].second;
int dist_0=d[i].first;
int dist_l=getDistance(most_left,pos);
int dist_r=getDistance(pos,most_right);
//cout<<"pos= "<<pos<<" dist_0= "<<dist_0<<" dist_l= "<<dist_l<<" dist_r= "<<dist_r<<endl;
pair<int,int> possible_l={my_location[most_right]-(dist_r),1};
pair<int,int> possible_r={my_location[most_left]+(dist_l),2};
//cout<<"possible_l: "<<possible_l.first<<" "<<possible_l.second<<" possible_r: "<<possible_r.first<<" "<<possible_r.second<<endl;
//test whether possible_l is valid
my_location[pos]=possible_l.first;
my_stype[pos]=possible_l.second;
//cout<<"manual "<<pos<<" "<<most_left<<" found: "<<manual_dist(pos,most_left)<<" wanted: "<<dist_l<<endl;
if(manual_dist(pos,most_left)==dist_l&&manual_dist(pos,most_right)==dist_r&&manual_dist(pos,0)==dist_0);
else
{
my_location[pos]=possible_r.first;
my_stype[pos]=possible_r.second;
}
if(my_stype[pos]==1)
{
if(my_location[pos]<my_location[most_left])most_left=pos;
}
else
{
if(my_location[pos]>my_location[most_right])most_right=pos;
}
//cout<<pos<<" -> "<<my_location[pos]<<" "<<my_stype[pos]<<endl;
}
for(int i=0;i<N;i++)
{
location[i]=my_location[i];
stype[i]=my_stype[i];
}
for(int i=0;i<N;i++)
location[i]+=first;
//for(int i=0;i<N;i++)cout<<i<<" -> "<<location[i]<<" "<<stype[i]<<endl;
}
/*
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;
}
*/
