#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[109][109];
int dist(int a, int b){
if(memo[a][b] != -1) return memo[a][b];
return memo[a][b] = getDistance(a,b);
}
void findLocation(int N, int first, int location[], int stype[]){
for(int i = 0; i < 109; i++){
for(int j = 0; j < 109; j++){
memo[i][j] = -1;
}
}
stype[0] = 1;
location[0] = first;
int stat = 0;
int maxi = INT_MAX;
for(int i = 1; i < N; i++){
if(maxi > dist(0,i)){
maxi = dist(0,i);
stat = i;
}
}
int fS = stat;
int fM = maxi;
stype[stat] = 2;
location[stat] = first+maxi;
int Stat = 0;
int Maxi = INT_MAX;
for(int i = 1; i < N; i++){
if(stat == i) continue;
if(Maxi > dist(stat,i) && dist(stat, i) > maxi){
Maxi = dist(stat, i);
Stat = i;
}
}
int Done = 3;
stype[Stat] = 1;
location[Stat] = first+maxi-Maxi;
vector<bool> done(N,false);
done[0] = true;
done[stat] = true;
done[Stat] = true;
Maxi = Maxi-maxi;
while(Done < N){
//cout << "Donnée " << stat << ' ' << maxi << ' ' << Stat << ' ' << Maxi << endl;
//cout << endl;
for(int i = 1; i < N; i++){
if(done[i]) continue;
//cout << i << ' ' << dist(stat,i) << endl;
if(dist(stat,i) < maxi && dist(0,i) == dist(0,stat)+dist(stat,i)){
Done++;
done[i] = true;
location[i] = first+dist(0,stat)-dist(stat,i);
stype[i] = 1;
}
}
for(int i = 1; i < N; i++){
if(done[i]) continue;
//cout << dist(Stat, i) << ' ' << dist(0, i) << ' ' << dist(0,Stat) <<endl;
if(dist(Stat, i) < Maxi && dist(Stat,i) == dist(0, i)-dist(0,Stat)){
Done++;
done[i] = true;
location[i] = location[Stat]+dist(Stat,i);
stype[i] = 2;
}
}
//cout << endl;
int tstat = -1;
int tmax = INT_MAX;
int tStat= -1;
int tMax = INT_MAX;
for(int i = 1; i < N; i++){
if(done[i]) continue;
if(dist(0,i) != dist(fS, i)+dist(0,fS) && dist(0,i) < tmax){
tmax = dist(0,i);
tstat = i;
}else if(dist(0,i) == dist(fS, i)+dist(0,fS) && dist(0,i) < tMax){
tMax = dist(0,i);
tstat = i;
}
}
if(tstat != -1){
stype[tstat] = 2;
location[tstat] = dist(0, tstat);
}
if(tStat != -1){
stype[tStat] = 1;
location[tStat] = first-(dist(0,tStat)-2*dist(0,fS));
}
stat = tstat;
maxi = tmax-maxi;
Stat = tStat;
Maxi = tMax-2*dist(0, fS)-Maxi;
}
}
/*
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];
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
*/
