#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
using Int=int;
#define int ll
// #define N 
const int N=1000005;
using namespace std;
int a[N],b[N],sa[N],sb[N],ans[N];
int Ans[N];
int cj(pa x,pa y)
{
	return x.fi*y.se-x.se*y.fi;
}
pa del(pa x,pa y)
{
	return mp(x.fi-y.fi,x.se-y.se);
}
std::vector<Int> testset(std::vector<Int> A, std::vector<Int> B, std::vector<Int> L, std::vector<Int> U)
{
	map<int,poly>G;
	for (int i=0;i<sz(L);i++)
		G[L[i]+1].push_back(i);
	for (int i=0;i<sz(A);i++) a[i+1]=A[i];
	for (int i=0;i<sz(B);i++) b[i+1]=B[i];
	int n=A.size();
	for (int i=1;i<=n;i++) sa[i]=sa[i-1]+a[i],sb[i]=sb[i-1]+b[i];
	for (int i=1;i<=n;i++)
	{
		if (G[i].empty()) continue;
		int ans=inf;
		vector<pa>sta;
		sort(G[i].begin(),G[i].end(),[&](int x,int y)
		{
			return U[x]>U[y];
		});
		sta.push_back(mp(i-1,sa[i-1]+sb[i-1]-b[i-1]));
		for (int j=i;j<=n;j++)
		{
			// cout<<i<<","<<j<<endl;
			pa now=mp(j,sa[j]+sb[j]);
			now=mp(j,sa[j]+sb[j]-b[j]);
			while (sta.size()>=2&&cj(del(now,sta[sta.size()-2]),del(now,sta[sta.size()-1]))>0)
			{
				ans=min(ans,(now.se+b[j]-sta.back().se)/(now.fi-sta.back().fi));
				sta.pop_back();
			}
			if (sz(sta))
			{
				int nw=inf;
				int l=0,r=sz(sta)-1;
				int res=0;now=mp(j,sa[j]+sb[j]);
				while (l<r)
				{
					int mid=l+(r-l)/2;
					if (cj(del(now,sta[mid]),del(now,sta[mid+1]))>0)
					{
						r=mid;
					} else l=mid+1;
				}
				now.se-=b[j];
				{
					int k=l;
					ans=min(ans,(now.se+b[j]-sta[k].se)/(now.fi-sta[k].fi));
					nw=(now.se+b[j]-sta[k].se)/(now.fi-sta[k].fi);
				}
			}
			sta.push_back(now);
			while (G[i].size()&&U[G[i].back()]+1==j)
			{
				Ans[G[i].back()]=ans;
				G[i].pop_back();
			}
			if (G[i].empty()) break;
		}
	}
	vector<Int>res;
	for (int i=0;i<sz(L);i++) res.push_back(Ans[i]);
	return res;
}