#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
/*
int diste[109][109];
int getDistance(int a, int b){
return diste[a][b];
}
*/
int memo[5009][5009];
int dist(int a, int b){
if(memo[a][b]) return memo[a][b];
return memo[a][b] = getDistance(a,b);
}
void findLocation(int N, int first, int location[], int stype[]){
stype[0] = 1;
location[0] = first;
vector< pair<int, int> > v(0);
for(int i = 1; i < N; i++){
v.push_back({dist(0,i), i});
}
sort(v.begin(), v.end());
int second = v[0].second;
location[second] = first+dist(0,second);
stype[second] = 2;
int R = second;
set< pair<int, int> > r;
int L = 0;
set< pair<int, int> > l;
r.insert(make_pair(location[R], R));
l.insert(make_pair(location[L], L));
//cout << L << ' ' << R << endl;
for(int it = 1; it < N-1; it++){
int i = v[it].second;
if(dist(0,i) == dist(0,second)+dist(second,i) && dist(second,i) > dist(0,second)){
//LEFT
// cout << "Left " << i << endl;
int p = location[L]+dist(L,i);
auto t = lower_bound(l.begin(), l.end(), make_pair(p,0));
t--;
auto vale = *t;
int val = vale.second;
//cout << p << ' ' << val << endl;
int d = p-vale.first;
if(dist(0,second)+dist(second, val)+d == dist(0,i)){
location[i] = p;
stype[i] = 2;
}else{
stype[i] = 1;
L = i;
location[i] = first-(dist(0,i)-2*dist(0,second));
l.insert(make_pair(location[i],i));
}
}else{
//RIGHT
//cout << "Right " << i << endl;
int p = location[R]-dist(R,i);
//for(auto a : r) cout << a.first << ' ' << a.second << endl;
auto t = lower_bound(r.begin(), r.end(), make_pair(p,-1));
auto vale = *t;
int val = vale.second;
//cout << p << ' ' << val << endl;
int d = vale.first-p;
if(dist(0,i) == dist(0,val)+d){
location[i] = location[val]-d;
stype[i] = 1;
}else{
R = i;
stype[i] = 2;
location[i] = first+dist(0,i);
r.insert(make_pair(location[i], i));
}
}
}
}
/*
int main(){
int n;
cin >> n;
int first;
cin >> first;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> diste[i][j];
}
}
int location[n];
int stype[n];
for(int i = 0; i < n; i++){
location[i] = INT_MAX;
stype[i] = INT_MAX;
}
findLocation(n,first, location,stype);
cout << endl;
for(int a : location) cout << a << ' ';
cout << endl;
for(int a : stype) cout << a << ' ';
cout << endl;
}
/*
5 4
0 12 4 15 7
12 0 8 3 11
4 8 0 11 3
15 3 11 0 14
7 11 3 14 0
*/
