#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
#define sp " "
#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt","w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define LL node * 2
#define RR node * 2
#define mid (l + r) / 2
#define ll long long
#define MAXN 200005
const int modulo = 1e9 + 7;
const ll INF = 2e18 +7;
int getDistance(int x,int y);
void findLocation(int N, int first, int location[], int stype[])
{
vector<int> dist1(N, 0), done(N, 0);
pii mini = {modulo, 0};
for (int i = 1; i < N; i++){
dist1[i] = getDistance(0, i);
mini = min(mini, {dist1[i], i});
}
int D = mini.nd;
stype[D] = 2;
stype[0] = 1;
location[D] = mini.st + first;
location[0] = first;
done[0] = done[D] = 1;
vector<int> dist2(N, 0);
dist2[0] = dist1[D];
mini = {first, 0};
for (int i = 1; i < N; i++){
if (i == D) continue;
dist2[i] = getDistance(D, i);
if (dist1[i] == dist2[i] + dist1[D]){
stype[i] = 1; //C
location[i] = location[D] - dist2[i];
done[i] = 1;
mini = min(mini, {location[i], i});
}
}
for (int i = 1; i < N; i++){
if (done[i]) continue;
if (dist2[i] == dist1[D] + dist1[i]){
stype[i] = 2; //D
location[i] = first + dist1[i];
done[i] = 1;
}
}
//Now we know the leftmost C
int C = mini.nd;
vector<int> dist3(N, 0);
for (int i = 0; i < N; i++){
if (done[i]) continue;
dist3[i] = getDistance(C, i);
if (dist3[i] + dist1[i] == first - location[C]){
stype[i] = 2; // D
location[i] = location[C] + dist3[i];
done[i] = 1;
}
else{
stype[i] = 1; //C
location[i] = location[D] + dist2[i];
done[i] = 1;
}
}
return;
}
/*
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 main()
{
fileio();
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 (int i = 0; i < S; i++){
cout<<"("<<type[i]<<sp<<location[i]<<") ";
}
cout<<endl;
for (int i = 0; i < S; i++){
cout<<"("<<stations[i].type<<sp<<stations[i].location<<") ";
}
cout<<endl;
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;
}
*/
