#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod = 1000000007 ;
const int mod1 = 998244353 ;
const int N = 6e6 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
#include "rail.h"
//#include "grader.h"
//typedef struct Station {
// int index;
// int type;
// int location;
// int L, R;
//} STATION;
//static long long cnt;
//static int S, SUBTASK;
//static STATION stations[10004];
//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;
//}
map < int , int > been ;
int d[ 5005 ][ 5005 ] ;
void findLocation(int n, int pos, int ps[], int tp[]){
ps[ 0 ] = pos ;
tp[ 0 ] = 1 ;
if( n == 1 ) return ;
vector < pair < int , int > > v ;
for( int i = 1 ; i < n ; i ++ ){
int x = getDistance( 0 , i ) ;
d[ 0 ][ i ] = x ;
d[ i ][ 0 ] = d[ 0 ][ i ] ;
v.pb( { x , i } ) ;
}
sort( v.begin() , v.end() ) ;
vector < int > ri , li ;
int x = v[ 0 ].s ;
for( auto yy : v ){
int y = yy.s ;
if( yy == v[ 0 ] ){
d[ x ][ 0 ] = v[ 0 ].f ;
}
if( yy == v[ 0 ] ) continue ;
d[ x ][ y ] = getDistance( x , y ) ;
d[ y ][ x ] = d[ x ][ y ] ;
if( d[ x ][ y ] < d[ x ][ 0 ] ){
ri.pb( y ) ;
continue ;
}
// cout << y << " " << d[ 0 ][ y ] << " " << d[ 0 ][ x ] << " " << d[ x ][ y ] << endl ;
if( d[ 0 ][ y ] == d[ 0 ][ x ] + d[ x ][ y ] ){
li.pb( y ) ;
continue ;
}
ri.pb( y ) ;
continue ;
}
pair < int , int > l , r ;
l = { pos , 0 } ;
been[ pos ] = 1 ;
r = { pos + v[ 0 ].f , v[ 0 ].s } ;
been[ pos + v[ 0 ].f ] = 2 ;
ps[ v[ 0 ].s ] = pos + v[ 0 ].f ;
tp[ v[ 0 ].s ] = 2 ;
int y = v[ 0 ].s ;
int cur = v[ 0 ].f + pos ;
// debug ;
for( auto x : ri ){
// cout << x <<endl ;
d[ y ][ x ] = getDistance( y , x ) ;
d[ x ][ y ] = d[ y ][ x ] ;
int z = d[ 0 ][ x ] - d[ 0 ][ y ] - d[ y ][ x ] ;
z /= 2 ;
int pos = cur + z ;
if( been[ pos ] != 2 ){
cur = d[ 0 ][ x ] + ps[ 0 ] ;
been[ cur ] = 2 ;
y = x ;
tp[ x ] = 2 ;
ps[ x ] = cur ;
continue ;
}
else{
tp[ x ] = 1 ;
int pps = cur - d[ y ][ x ] ;
been[ pps ] = 1 ;
ps[ x ] = pps ;
continue ;
}
// cout << ps[ x ] << " " << tp[ x ] << endl ;
}
int cr = ps[ 0 ] ;
int ll = 0 ;
y = v[ 0 ].s ;
x = y ;
for( auto z : li ){
d[ ll ][ z ] = getDistance( ll , z ) ;
d[ z ][ ll ] = d[ ll ][ z ] ;
int Z = d[ x ][ z ] - d[ x ][ ll ] - d[ ll ][ z ] ;
Z /= 2 ;
int pos = cr - Z ;
if( been[ pos ] != 1 ){
tp[ z ] = 1 ;
int pss = ps[ x ] - d[ x ][ z ] ;
been[ pss ] = 1 ;
if( pss < cr ){
ll = z ;
}
cr = min( cr , pss ) ;
ps[ z ] = pss ;
}
else{
tp[ z ] = 2 ;
int pss = cr + d[ ll ][ z ] ;
been[ pss ] = 2 ;
ps[ z ] = pss ;
}
}
return ;
}
/*
2
6
1 3
2 6
2 7
1 1
1 0
2 8
*/
//static 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;
//}
//
//static 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;
//}
//
//static 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;
// }
//}
//
//
//
//static void getInput() {
// assert(scanf("%d", &SUBTASK) == 1);
// assert(scanf("%d", &S) == 1);
// int s;
// for (s = 0; s < S; s++) {
// int type, location;
// assert(scanf(" %d %d", &type, &location) == 2);
// 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);
//}
//
//static int serverGetFirstStationLocation() { return stations[0].location; }
//
//static int location[10005];
//static int type[10005];
//static int ok = 1;
//
//int main() {
// int i;
// getInput();
// cnt = 0;
//
// 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;
//}
