/* This is sample grader for the contestant */
#include <bits/stdc++.h>
#include "rail.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;
//}
const int N = 5010;
int d[N][N];
void findLocation(int n, int first, int location[], int stype[]) {
memset(d, -1, sizeof(d));
auto get = [&](int u, int v) {
if (u == v) return 0;
if (d[u][v] == -1) d[u][v] = getDistance(u, v);
return d[u][v];
};
for (int i = 0; i < n; ++i) location[i] = -1;
int R = 1;
location[0] = first;
stype[0] = 1;
for (int i = 1; i < n; ++i)
if (get(0, i) < get(0, R)) R = i;
location[R] = first + get(0, R);
stype[R] = 2;
int L = 0;
for (int i = 0; i < n; ++i)
if (R != i && get(i, R) < get(L, R)) L = i;
location[L] = location[R] - get(L, R);
stype[L] = 1;
for (int i = 0; i < n; ++i) {
if (i == first || i == L || i == R) continue;
if (get(L, i) == get(L, R) + get(R, i)) {
location[i] = location[R] - get(R, i);
stype[i] = 1;
}
if (get(R, i) == get(R, L) + get(L, i)) {
location[i] = location[L] + get(L, i);
stype[i] = 2;
}
}
for (int i = 0; i < n; ++i) {
if (location[i] != -1) continue;
int k = -1;
for (int j = 0; j < n; ++j) {
if (location[j] == -1) continue;
if (k == -1 || get(i, j) < get(i, k)) k = j;
}
assert(k != -1);
stype[i] = 3 - stype[k];
if (stype[i] == 2) location[i] = location[k] + get(i, k);
else location[i] = location[k] - get(i, k);
}
}
//
//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()
//{
// 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;
//}
