//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
#include "rail.h"
int it[5001][5001];
int vis[5001];
int getdistance(int i,int j){
if(it[i][j]==-1){
it[i][j]=getDistance(i,j);
return it[i][j];
}
else{
return it[i][j];
}
}
void findLocation(int n, int x, int aa[], int bb[])
{
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
it[i][j]=-1;
}
}
aa[0]=x;
bb[0]=1;
for(int i=1;i<n;i++){
bb[i]=2;
}
vis[0]=1;
// int cur=0;
pair<int,int> mi;
mi.b=-1;
for(int i=0;i<n;i++){
if(vis[i]==0){
getdistance(0,i);
if(mi.b==-1){
mi={it[0][i],i};
}
else{
mi=min(mi,{it[0][i],i});
}
}
}
int yy=0;
vector<pair<int,int>> ss;
vector<pair<int,int>> ee;
//cout<<mi.a<<":"<<mi.b<<endl;
int ne=mi.b;
it[mi.b][0]=it[0][mi.b];
for(int i=1;i<n;i++){
if(mi.b!=i){
int xx=getdistance(mi.b,i);
if(it[0][i]==mi.a+xx){
if(xx<it[0][mi.b]){
bb[i]=1;
vis[i]=1;
aa[i]=aa[0]+mi.a-xx;
}
else{
ee.pb({it[mi.b][i],i});
yy++;
}
continue;
}
else{
ss.pb({it[0][i],i});
}
}
else if(mi.b==i){
aa[i]=it[0][i]+aa[0];
}
}
sort(ss.begin(),ss.end());
//reverse(ss.begin(),ss.end());
/*for(auto j:ss){
cout<<j.a<<".."<<j.b<<endl;
}*/
sort(ee.begin(),ee.end());
//reverse(ee.begin(),ee.end());
vector<pair<int,int>> zz;
int cur=mi.b;
map<int,int> ac;
ac[aa[mi.b]]++;
for(auto j:ss){
getdistance(0,j.b);
getdistance(0,cur);
int x=getdistance(cur,j.b);
int z=it[0][cur]+x-it[0][j.b];
if(ac.find(aa[cur]-(z/2))!=ac.end()){
aa[j.b]=aa[cur]-x;
bb[j.b]=1;
}
else{
aa[j.b]=aa[0]+it[0][j.b];
ac[aa[j.b]]++;
cur=j.b;
}
/* if(x<it[0][cur]){
aa[j.b]=aa[cur]-x;
bb[j.b]=1;
}
else{
aa[j.b]=aa[0]+it[0][j.b];
cur=j.b;
}*/
}
ac.clear();
ac[aa[0]]++;
cur=0;
for(auto j:ee){
getdistance(mi.b,j.b);
getdistance(mi.b,cur);
int x=getdistance(cur,j.b);
int z=it[mi.b][cur]+x-it[mi.b][j.b];
//cout<<j.b<<":"<<z<<endl;
// cout<<cur<<endl;
//cout<<it[mi.b][cur]<<",,"<<it[cur][j.b]<<",,"<<it[mi.b][j.b]<<endl;
if(ac.find(aa[cur]+(z/2))!=ac.end()){
aa[j.b]=aa[cur]+x;
}
else{
aa[j.b]=aa[mi.b]-it[mi.b][j.b];
ac[aa[j.b]]++;
bb[j.b]=1;
cur=j.b;
}
/* if(x<it[0][cur]){
aa[j.b]=aa[cur]-x;
bb[j.b]=1;
}
else{
aa[j.b]=aa[0]+it[0][j.b];
cur=j.b;
}*/
}
/*while(ss.size()){
if(ss.size()==1){
aa[ss.back().b]=aa[0]+it[0][ss.back().b];
//bb[ss.back().b]=2;
break;
}
int x=getdistance(ss[ss.size()-2].b,ss[ss.size()-1].b);
if(x+it[0][ss[ss.size()-2].b]==it[0][ss[ss.size()-1].b]){
zz.pb({ss[ss.size()-2].b,ss[ss.size()-1].b});
bb[ss.back().b]=1;
cout<<ss.back().a<<"<"<<ss.back().b<<endl;
}
else{
aa[ss.back().b]=aa[0]+it[0][ss.back().b];
}
ss.pop_back();
}
reverse(zz.begin(),zz.end());
for(auto j:zz){
cout<<j.a<<"::"<<j.b<<endl;
}
while(zz.size()){
aa[zz.back().b]=aa[zz.back().a]-it[zz.back().a][zz.back().b];
zz.pop_back();
}
//cout<<bb[mi.b]<<endl;
while(ee.size()){
if(ee.size()==1){
aa[ee.back().b]=aa[mi.b]-it[mi.b][ee.back().b];
bb[ee.back().b]=1;
break;
}
int x=getdistance(ee[ee.size()-2].b,ee[ee.size()-1].b);
if(x+it[mi.b][ee[ee.size()-2].b]==it[mi.b][ee[ee.size()-1].b]){
zz.pb({ee[ee.size()-2].b,ee[ee.size()-1].b});
}
else{
aa[ee.back().b]=aa[mi.b]-it[mi.b][ee.back().b];
//cout<<ee.back().b<<endl;
bb[ee.back().b]=1;
}
ee.pop_back();
}
reverse(zz.begin(),zz.end());
while(zz.size()){
aa[zz.back().b]=aa[zz.back().a]+it[zz.back().a][zz.back().b];
zz.pop_back();
}*/
/* while(ss.size()){
mi={0,0};
mi.b=-1;
for(auto i:ss){
getdistance(0,i);
if(mi.b==-1){
mi={it[0][i],i};
}
else{
mi=min(mi,{it[0][i],i});
}
}
vector<int> tt;
for(auto i:ss){
if(mi.b!=i){
int xx=getDistance(mi.b,i);
if(it[0][i]==mi.a+xx){
bb[i]=1;
vis[i]=1;
aa[i]=aa[0]+mi.a-xx;
continue;
}
else{
tt.pb(i);
}
}
else if(mi.b==i){
aa[i]=it[0][i]+aa[0];
}
}
ss=tt;
}
if(ee.size()){
mi.b=-1;
for(auto i:ee){
getdistance(ne,i);
if(mi.b==-1){
mi={it[ne][i],i};
}
else{
mi=min(mi,{it[ne][i],i});
}
}
ss.clear();
for(auto i:ee){
if(mi.b!=i){
int xx=getDistance(mi.b,i);
if(it[ne][i]==mi.a+xx){
vis[i]=1;
aa[i]=aa[ne]-mi.a+xx;
continue;
}
else{
ss.pb(i);
}
}
else if(mi.b==i){
bb[i]=1;
aa[i]=-it[ne][i]+aa[ne];
}
}
while(ss.size()){
mi={0,0};
mi.b=-1;
for(auto i:ss){
getdistance(ne,i);
if(mi.b==-1){
mi={it[ne][i],i};
}
else{
mi=min(mi,{it[ne][i],i});
}
}
vector<int> tt;
for(auto i:ss){
if(mi.b!=i){
int xx=getDistance(mi.b,i);
if(it[ne][i]==mi.a+xx){
vis[i]=1;
aa[i]=aa[ne]-(mi.a-xx);
continue;
}
else{
tt.pb(i);
}
}
else if(mi.b==i){
bb[i]=1;
aa[i]=-it[ne][i]+aa[ne];
}
}
ss=tt;
}
}
*/
/*
for(int i=0;i<n;i++){
cout<<aa[i]<<":";
}
cout<<endl;
for(int i=0;i<n;i++){
cout<<bb[i]<<":";
}
cout<<endl;
*/
}
