//#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<int> ss;
vector<int> ee;
//cout<<mi.a<<":"<<mi.b<<endl;
int ne=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(2*xx<it[0][i]){
bb[i]=1;
vis[i]=1;
aa[i]=aa[0]+mi.a-xx;
}
else{
ee.pb(i);
yy++;
}
continue;
}
else{
ss.pb(i);
}
}
else if(mi.b==i){
aa[i]=it[0][i]+aa[0];
}
}
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;
*/
}
