#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back #define ppc __builtin_popcount using namespace std; typedef long long ll; typedef unsigned long long ull; typedef unsigned int uint; const int maxn=1e6+10,mod=998244353; const int N=2e6+10;const ll inf=1e18; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n; struct nd { int a,b; }; ll lm[maxn],sm[maxn],dp[maxn]; int F(ll u){ int p=upper_bound(lm+1,lm+n+1,u)-lm-1;u+=sm[p]; int q=upper_bound(dp+1,dp+n+1,u)-dp-1; return p+q; } mt19937 rng(0); struct treap { int rt,tot; struct nd { int ls,rs,rnd; ll dt,sdt,siz; }d[maxn]; int nnd(ll v){ int u=++tot; d[u].ls=d[u].rs=0,d[u].rnd=rng(); d[u].dt=d[u].sdt=v,d[u].siz=1; return u; } void pu(int p){ d[p].siz=d[d[p].ls].siz+d[d[p].rs].siz+1; d[p].sdt=d[d[p].ls].sdt+d[d[p].rs].sdt+d[p].dt; d[p].sdt=min(d[p].sdt,inf); } void spsdt(int u,ll k,int &p,int &q){ if(!u)return p=q=0,void(); if(k>=d[d[u].ls].sdt+d[u].dt)p=u,spsdt(d[u].rs,k-d[d[u].ls].sdt-d[u].dt,d[p].rs,q),pu(p); else q=u,spsdt(d[u].ls,k,p,d[q].ls),pu(q); } void spdt(int u,ll k,int &p,int &q){ if(!u)return p=q=0,void(); if(k>=d[u].dt)p=u,spdt(d[u].rs,k,d[p].rs,q),pu(p); else q=u,spdt(d[u].ls,k,p,d[q].ls),pu(q); } void sps(int u,int k,int &p,int &q){ if(!u)return p=q=0,void(); if(k>=d[d[u].ls].siz+1)p=u,sps(d[u].rs,k-d[d[u].ls].siz-1,d[p].rs,q),pu(p); else q=u,sps(d[u].ls,k,p,d[q].ls),pu(q); } int mg(int p,int q){ if((!p)||(!q))return p|q; if(d[p].rnd<d[q].rnd){ d[p].rs=mg(d[p].rs,q);pu(p);return p; }else { d[q].ls=mg(p,d[q].ls);pu(q);return q; } } void add(ll a,ll b){ int p=0,q=0,r=0; spsdt(rt,b,p,q); if(!q)return rt=p,void(); spdt(q,a-b,q,r); //cout<<"test "<<d[p].siz<<" "<<d[q].siz<<" "<<d[r].siz<<endl; if(r){ int o=0,v=0; if(q)sps(r,d[r].siz-1,r,o),r=mg(nnd(a-b),r); else { int l=0; sps(r,1,l,r); d[l].dt=d[l].sdt=a-b+d[l].dt-(a-d[p].sdt); r=mg(nnd(a-d[p].sdt),mg(l,r)); sps(r,d[r].siz-1,r,o); } } rt=mg(p,mg(q,r)); } ll s; int top; void dfs(int u){ if(d[u].ls)dfs(d[u].ls); s+=d[u].dt,s=min(s,inf),dp[top++]=s; if(d[u].rs)dfs(d[u].rs); } }T; int a[maxn],b[maxn]; void slv(){ n=read(); up(i,1,n)a[i]=read(); up(i,1,n)b[i]=read(); vector<nd>L,R; up(i,1,n){ nd x;x.a=a[i],x.b=b[i]; if(x.a<=x.b)L.p_b(x); else R.p_b(x); } sort(L.begin(),L.end(),[](nd x,nd y){return x.a<y.a;}); sort(R.begin(),R.end(),[](nd x,nd y){return x.b<y.b;}); memset(lm,0x3f,sizeof(lm));lm[0]=0; ll s=0,lim=0; up(i,1,(int)L.size()){ lim=max(lim,L[i-1].a-s),lm[i]=lim; s=s-L[i-1].a+L[i-1].b,sm[i]=s; } T.rt=T.nnd(0); up(i,1,n){ T.rt=T.mg(T.rt,T.nnd(inf)); } for(auto it:R){ //cout<<"+ "<<it.a<<" "<<it.b<<endl; T.add(it.a,it.b); //T.dfs(T.rt); //up(i,1,n)cout<<dp[i]<<" ";cout<<endl; //T.s=T.top=0; } T.dfs(T.rt); //cout<<dp[0]<<endl; //up(i,1,n)cout<<dp[i]<<" ";cout<<endl; up(i,1,n){ ll l=0,r=1e18; while(l+1<r){ ll mid=l+r>>1; if(F(mid)<i)l=mid; else r=mid; } printf("%lld ",r); }printf("\n"); } int main(){ //freopen("1.in","r",stdin),freopen("1.out","w",stdout); //int t=read();while(t--)slv(); slv(); //cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; }