#include "multi.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll unsigned long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<unsigned long long, unsigned long long>
#define vi vector<int>
#define vl vector<unsigned long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int fint(int v, vi& rep_)
{
if(rep_[v] == v) return v;
return rep_[v] = fint(rep_[v],rep_);
}
void onion(int a, int b, vi& rep_)
{
if(a >= siz(rep_) || b >= siz(rep_)) return;
a = fint(a,rep_);
b = fint(b,rep_);
if(a < b) swap(a,b);
rep_[a] = b;
}
vector<ull> strategy(int n, int rr, int v, vector<ull> A, vector<ull> B)
{
vi rep_(n);
rep(i,n) rep_[i] = i;
ll ans = 0;
if(rr != 0)
{
if(rr == 1)
{
vector<pll> sd_best;
rep(i,n)
{
int v0 = B[i]%(1<<8);
B[i] /= (1<<8);
int v1 = B[i]%(1<<8);
B[i] /= (1<<8);
ll cost = B[i];
onion(i,v0,rep_);
sd_best.pb({cost,v1});
}
map<int,vi> ls;
rep(i,n) ls[fint(i,rep_)].pb(i);
forall(it,ls)
{
if(siz(it.ss) == 2)
{
pll best = min(sd_best[it.ss[0]],sd_best[it.ss[1]]);
if(fint(it.ss[0],rep_) != fint(best.ss,rep_))
{
ans += best.ff;
onion(it.ss[0],best.ss,rep_);
}
}
}
}
else if(rr <= 3)
{
rep(i,n) rep_[i] = 0;
rep(i,8) if(B[v]&(1<<i)) rep_[v] += (1<<i);
rep(i,56) if(B[v]&(1ULL<<(ll)(i+8))) ans += (1ULL<<(ll)i);
rep(x,n) if(x != v) rep(i,8) if(B[x]&(1<<i)) rep_[x] += (1<<i);
map<int,pll> best_edges;
rep(i,n) best_edges[rep_[i]] = {1e18,rep_[i]};
rep(x,n)
{
if(x == v) continue;
int gdzie = 0;
ll cost = 0;
rep(i,48) if(B[x]&(1ULL<<(ll)i+8)) cost += (1ULL<<(ll)i);
rep(i,8) if(B[x]&(1ULL<<(ll)(i+56))) gdzie += (1ULL<<(ll)i);
best_edges[rep_[x]] = min(best_edges[rep_[x]],{cost,rep_[gdzie]});
best_edges[rep_[gdzie]] = min(best_edges[rep_[gdzie]],{cost,rep_[x]});
}
rep(x,n)
{
if(rep_[v] == rep_[x]) continue;
best_edges[rep_[v]] = min(best_edges[rep_[v]],{A[x],rep_[x]});
best_edges[rep_[x]] = min(best_edges[rep_[x]],{A[x],rep_[v]});
}
vector<pair<ll,pii>> vs;
forall(it,best_edges)
{
int a = it.ff;
int b = it.ss.ss;
ll c = it.ss.ff;
vs.pb({c,{a,b}});
}
sort(all(vs));
forall(it,vs)
{
int a = it.ss.ff;
int b = it.ss.ss;
ll c = it.ff;
if(fint(a,rep_) != fint(b,rep_))
{
ans += c;
onion(a,b,rep_);
}
}
}
else if(rr == 4)
{
rep(i,n) rep_[i] = B[i]%(1<<8);
set<int> dif;
rep(i,n) dif.insert(rep_[i]);
vl ans2(n,rep_[v]);
if(v != n-1 && v != n-2 && v >= siz(dif)*(siz(dif)-1)/2) return ans2;
if(v == n-1)
{
ans2[v] = B[v];
return ans2;
}
if(v == n-2)
{
rep(i,n) rep_[i] = i;
ans = 0;
rep(i,n)
{
B[i] /= (1<<8);
int v2 = B[i]%(1<<8);
ll c = B[i]/(1<<8);
if(fint(i,rep_) != fint(v2,rep_))
{
ans += c;
onion(i,v2,rep_);
}
}
ans2[n-1] += ans*(1<<8);
return ans2;
}
ll best = 1e18;
rep(i,n) best = min(best,B[i]/(1<<8));
ans2[n-1] += best*(1<<8);
return ans2;
}
else
{
if(v != n-1)
{
vl xd(n,0);
return xd;
}
rep(i,n) rep_[i] = B[i]%(1<<8);
set<int> dif;
rep(i,n) dif.insert(rep_[i]);
rep(i,n) rep_[i] = i;
vector<pair<ll,pii>> edges;
int cur = 0;
rep(i,siz(dif)) rep2(j,i+1,siz(dif)-1) edges.pb({B[cur++]/(1<<8),{i,j}});
sort(all(edges));
ans = B[v]/(1<<8)+B[n-2]/(1<<8);
forall(it,edges)
{
int a = it.ss.ff;
int b = it.ss.ss;
ll c = it.ff;
if(fint(a,rep_) != fint(b,rep_))
{
ans += c;
onion(a,b,rep_);
}
}
return {ans};
}
}
rep(i,n) fint(i,rep_);
if(rr == 0)
{
vector<pll> best = {{(1ULL<<(ll)48)-1,v}};
rep(i,n) if(i != v) best.pb({A[i],i});
sort(all(best));
ll send = best[0].ss+best[1].ss*(1<<8)+best[1].ff*(1ULL<<(ll)16);
vl ans2(n,send);
return ans2;
}
else if(rr <= 2)
{
pll best = {1e18,rep_[v]};
rep(i,n) if(rep_[i] != rep_[v]) best = min(best,{A[i],rep_[i]});
vl ans2(n,0);
rep(i,8) if(rep_[v]&(1<<i)) ans2[v] += (1<<i);
rep(i,56) if(ans&(1ULL<<(ll)i)) ans2[v] += (1ULL<<(ll)(i+8));
rep(x,n)
{
if(x == v) continue;
rep(i,8) if(rep_[v]&(1<<i)) ans2[x] += (1<<i);
rep(i,48) if(best.ff&(1ULL<<(ll)i)) ans2[x] += (1ULL<<(ll)(i+8));
rep(i,8) if(best.ss&(1ULL<<(ll)i)) ans2[x] += (1ULL<<(ll)(i+56));
}
return ans2;
}
else
{
map<int,int> mp;
rep(i,n) mp[rep_[i]] = 1;
int cur = 0;
forall(it,mp) mp[it.ff] = cur++;
rep(i,n) rep_[i] = mp[rep_[i]];
vl ans2(n,rep_[v]);
if(v == n-1) ans2[v] += ans*(1<<8);
map<int,ll> best_edge;
rep(i,n) best_edge[rep_[i]] = 1e18;
rep(i,n) best_edge[rep_[i]] = min(best_edge[rep_[i]],A[i]);
cur = 0;
rep(i,siz(mp)) rep2(j,i+1,siz(mp)-1)
{
if(i != rep_[v] && j != rep_[v])
{
ans2[cur] += (((1ULL<<(ll)48)-1)<<(ll)8);
cur++;
continue;
}
ans2[cur] += best_edge[(i != rep_[v] ? i : j)]*(1<<8);
cur++;
}
pll best = {1e18,-1};
rep(i,n) if(i != v) best = min(best,{A[i],i});
ans2[n-2] += best.ss*(1<<8)+best.ff*(1<<16);
return ans2;
}
}
