//longlong5a6
#include <bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
#define bit(i, x)((x >> i) & 1)
#define sobit(i) __builtin_popcount((int)(i))
#define pb push_back
#define vi vector<int>
#define For(i,x,n) for(int (i)=(int)(x);(i)<=(int)(n);(i)++)
#define round(m,n) setprecision((int)m) << fixed << double(n)
#define down "\n"
#define TASK "near"
#define maxn 200001
#define int long long
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
int n;
int a[maxn],b[maxn];
struct Knot
{
int F,S,val;
};
pii line[maxn];
vector<int> C;
int sum;
Knot val[maxn*8];
Knot T[maxn*8];
void push(int node)
{
T[node*2]=T[node*2+1]=val[node];
val[node*2]=val[node*2+1]=val[node];
val[node]= {0,0,0};
}
Knot get(int node,int l,int r,int u,int v)
{
if (v<l|u>r) return {0,0,0};
if (l>=u&&r<=v) return T[node];
if (val[node].F) push(node);
int mid=(l+r)/2;
Knot Trai=get(node*2,l,mid,u,v);
Knot Phai=get(node*2+1,mid+1,r,u,v);
Knot rt=Trai;
if (Phai.val>Trai.val) rt=Phai;
return rt;
}
void update(int node,int l,int r,int u,int v,Knot w)
{
if (r<u||v<l) return;
if (l>=u&&r<=v)
{
T[node]=w;
val[node]=w;
return;
}
if (val[node].F) push(node);
int mid=(l+r)/2;
update(node*2,l,mid,u,v,w);
update(node*2+1,mid+1,r,u,v,w);
T[node]=T[node*2];
if(T[node*2+1].val>T[node*2].val) T[node]=T[node*2+1];
}
void Init(int node,int l,int r)
{
T[node]= {0,0,0};
val[node]= {0,0,0};
if(l==r) return ;
int mid=(l+r)/2;
Init(node*2,l,mid);
Init(node*2+1,mid+1,r);
//T[node]=min(T[node*2],T[node*2+1]);
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie();
cout.tie();
if (fopen("in.txt","r"))
{
freopen("in.txt","r",stdin);
}
if (fopen(TASK".INP","r"))
{
freopen(TASK".INP","r",stdin);
freopen(TASK".OUT","w",stdout);
}
int t;
cin>>t;
while(t--)
{
C.clear();
sum=0;
cin>>n;
For(i,1,n)
{
cin>>a[i];
C.pb(a[i]);
}
For(i,1,n)
{
cin>>b[i];
C.pb(b[i]);
}
sort(C.begin(),C.end());
C.resize(unique(C.begin(),C.end())-C.begin());
For(i,1,n)
{
int g=lower_bound(C.begin(),C.end(),a[i])-C.begin()+1;
int k=lower_bound(C.begin(),C.end(),b[i])-C.begin()+1;
line[i]= {g,k};
}
int res;
For(i,1,n)
{
sum+=a[i]-b[i];
Knot G=get(1,1,n*2,line[i].S,line[i].S);
Knot K=get(1,1,n*2,line[i].F,line[i].F);
int nx=line[i].S;
int ny=line[i].F;
if(G.F!=0)
{
if(G.F<line[i].S) nx=G.F;
}
if(K.S!=0)
if(K.S>line[i].F) ny=K.S;
int ndis=C[ny-1]-C[nx-1];
update(1,1,n*2,nx,ny, {nx,ny,ndis});
res=get(1,1,n*2,1,n*2).val;
cout<<sum-res<<" ";
}
Init(1,1,2*n);
cout<<down;
}
}
Ly9sb25nbG9uZzVhNgojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBwaWkgcGFpcjxpbnQsaW50PgojZGVmaW5lIEYgZmlyc3QKI2RlZmluZSBTIHNlY29uZAojZGVmaW5lIGJpdChpLCB4KSgoeCA+PiBpKSAmIDEpCiNkZWZpbmUgc29iaXQoaSkgIF9fYnVpbHRpbl9wb3Bjb3VudCgoaW50KShpKSkKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSB2aSB2ZWN0b3I8aW50PgojZGVmaW5lIEZvcihpLHgsbikgZm9yKGludCAoaSk9KGludCkoeCk7KGkpPD0oaW50KShuKTsoaSkrKykKI2RlZmluZSByb3VuZChtLG4pIHNldHByZWNpc2lvbigoaW50KW0pIDw8IGZpeGVkIDw8IGRvdWJsZShuKQojZGVmaW5lIGRvd24gIlxuIgojZGVmaW5lIFRBU0sgIm5lYXIiCiNkZWZpbmUgbWF4biAyMDAwMDEKI2RlZmluZSBpbnQgbG9uZyBsb25nCiNwcmFnbWEgR0NDIHRhcmdldCAoImF2eDIiKQojcHJhZ21hIEdDQyBvcHRpbWl6YXRpb24gKCJPMyIpCiNwcmFnbWEgR0NDIG9wdGltaXphdGlvbiAoInVucm9sbC1sb29wcyIpCiNwcmFnbWEgR0NDIG9wdGltaXplKCJPZmFzdCxuby1zdGFjay1wcm90ZWN0b3IsdW5yb2xsLWxvb3BzLGZhc3QtbWF0aCxPMyIpCiNwcmFnbWEgR0NDIHRhcmdldCgic3NlLHNzZTIsc3NlMyxzc3NlMyxzc2U0LHBvcGNudCxhYm0sbW14LGF2eCxhdngyLHR1bmU9bmF0aXZlIikKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBuOwppbnQgYVttYXhuXSxiW21heG5dOwpzdHJ1Y3QgS25vdAp7CiAgICBpbnQgRixTLHZhbDsKfTsKcGlpIGxpbmVbbWF4bl07CnZlY3RvcjxpbnQ+IEM7CmludCBzdW07Cktub3QgdmFsW21heG4qOF07Cktub3QgVFttYXhuKjhdOwoKdm9pZCBwdXNoKGludCBub2RlKQp7CiAgICBUW25vZGUqMl09VFtub2RlKjIrMV09dmFsW25vZGVdOwogICAgdmFsW25vZGUqMl09dmFsW25vZGUqMisxXT12YWxbbm9kZV07CiAgICB2YWxbbm9kZV09IHswLDAsMH07Cn0KS25vdCBnZXQoaW50IG5vZGUsaW50IGwsaW50IHIsaW50IHUsaW50IHYpCnsKICAgIGlmICh2PGx8dT5yKSByZXR1cm4gezAsMCwwfTsKICAgIGlmIChsPj11JiZyPD12KSByZXR1cm4gVFtub2RlXTsKICAgIGlmICh2YWxbbm9kZV0uRikgcHVzaChub2RlKTsKICAgIGludCBtaWQ9KGwrcikvMjsKICAgIEtub3QgVHJhaT1nZXQobm9kZSoyLGwsbWlkLHUsdik7CiAgICBLbm90IFBoYWk9Z2V0KG5vZGUqMisxLG1pZCsxLHIsdSx2KTsKICAgIEtub3QgcnQ9VHJhaTsKICAgIGlmIChQaGFpLnZhbD5UcmFpLnZhbCkgcnQ9UGhhaTsKICAgIHJldHVybiBydDsKfQp2b2lkIHVwZGF0ZShpbnQgbm9kZSxpbnQgbCxpbnQgcixpbnQgdSxpbnQgdixLbm90IHcpCnsKICAgIGlmIChyPHV8fHY8bCkgcmV0dXJuOwogICAgaWYgKGw+PXUmJnI8PXYpCiAgICB7CiAgICAgICAgVFtub2RlXT13OwogICAgICAgIHZhbFtub2RlXT13OwogICAgICAgIHJldHVybjsKICAgIH0KICAgIGlmICh2YWxbbm9kZV0uRikgcHVzaChub2RlKTsKICAgIGludCBtaWQ9KGwrcikvMjsKICAgIHVwZGF0ZShub2RlKjIsbCxtaWQsdSx2LHcpOwogICAgdXBkYXRlKG5vZGUqMisxLG1pZCsxLHIsdSx2LHcpOwogICAgVFtub2RlXT1UW25vZGUqMl07CiAgICBpZihUW25vZGUqMisxXS52YWw+VFtub2RlKjJdLnZhbCkgVFtub2RlXT1UW25vZGUqMisxXTsKfQoKCnZvaWQgSW5pdChpbnQgbm9kZSxpbnQgbCxpbnQgcikKewogICAgVFtub2RlXT0gezAsMCwwfTsKICAgIHZhbFtub2RlXT0gezAsMCwwfTsKCiAgICBpZihsPT1yKSByZXR1cm4gOwogICAgaW50IG1pZD0obCtyKS8yOwogICAgSW5pdChub2RlKjIsbCxtaWQpOwogICAgSW5pdChub2RlKjIrMSxtaWQrMSxyKTsKICAgIC8vVFtub2RlXT1taW4oVFtub2RlKjJdLFRbbm9kZSoyKzFdKTsKCn0KCgoKc2lnbmVkIG1haW4oKQp7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOwogICAgY2luLnRpZSgpOwogICAgY291dC50aWUoKTsKICAgIGlmIChmb3BlbigiaW4udHh0IiwiciIpKQogICAgewogICAgICAgIGZyZW9wZW4oImluLnR4dCIsInIiLHN0ZGluKTsKCiAgICB9CiAgICBpZiAoZm9wZW4oVEFTSyIuSU5QIiwiciIpKQogICAgewogICAgICAgIGZyZW9wZW4oVEFTSyIuSU5QIiwiciIsc3RkaW4pOwogICAgICAgIGZyZW9wZW4oVEFTSyIuT1VUIiwidyIsc3Rkb3V0KTsKICAgIH0KICAgIGludCB0OwogICAgY2luPj50OwogICAgd2hpbGUodC0tKQogICAgewogICAgICAgIEMuY2xlYXIoKTsKICAgICAgICBzdW09MDsKICAgICAgICBjaW4+Pm47CiAgICAgICAgRm9yKGksMSxuKQogICAgICAgIHsKICAgICAgICAgICAgY2luPj5hW2ldOwogICAgICAgICAgICBDLnBiKGFbaV0pOwogICAgICAgIH0KICAgICAgICBGb3IoaSwxLG4pCiAgICAgICAgewogICAgICAgICAgICBjaW4+PmJbaV07CiAgICAgICAgICAgIEMucGIoYltpXSk7CiAgICAgICAgfQogICAgICAgIHNvcnQoQy5iZWdpbigpLEMuZW5kKCkpOwogICAgICAgIEMucmVzaXplKHVuaXF1ZShDLmJlZ2luKCksQy5lbmQoKSktQy5iZWdpbigpKTsKICAgICAgICBGb3IoaSwxLG4pCiAgICAgICAgewogICAgICAgICAgICBpbnQgZz1sb3dlcl9ib3VuZChDLmJlZ2luKCksQy5lbmQoKSxhW2ldKS1DLmJlZ2luKCkrMTsKICAgICAgICAgICAgaW50IGs9bG93ZXJfYm91bmQoQy5iZWdpbigpLEMuZW5kKCksYltpXSktQy5iZWdpbigpKzE7CiAgICAgICAgICAgIGxpbmVbaV09IHtnLGt9OwogICAgICAgIH0KICAgICAgICBpbnQgcmVzOwogICAgICAgIEZvcihpLDEsbikKICAgICAgICB7CiAgICAgICAgICAgIHN1bSs9YVtpXS1iW2ldOwogICAgICAgICAgICBLbm90IEc9Z2V0KDEsMSxuKjIsbGluZVtpXS5TLGxpbmVbaV0uUyk7CiAgICAgICAgICAgIEtub3QgSz1nZXQoMSwxLG4qMixsaW5lW2ldLkYsbGluZVtpXS5GKTsKICAgICAgICAgICAgaW50IG54PWxpbmVbaV0uUzsKICAgICAgICAgICAgaW50IG55PWxpbmVbaV0uRjsKICAgICAgICAgICAgaWYoRy5GIT0wKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpZihHLkY8bGluZVtpXS5TKSBueD1HLkY7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaWYoSy5TIT0wKQogICAgICAgICAgICBpZihLLlM+bGluZVtpXS5GKSBueT1LLlM7CiAgICAgICAgICAgIGludCBuZGlzPUNbbnktMV0tQ1tueC0xXTsKICAgICAgICAgICAgdXBkYXRlKDEsMSxuKjIsbngsbnksIHtueCxueSxuZGlzfSk7CiAgICAgICAgICAgIHJlcz1nZXQoMSwxLG4qMiwxLG4qMikudmFsOwogICAgICAgICAgICBjb3V0PDxzdW0tcmVzPDwiICI7CiAgICAgICAgfQogICAgICAgIEluaXQoMSwxLDIqbik7CiAgICAgICAgY291dDw8ZG93bjsKICAgIH0KfQo=