#include<bits/stdc++.h>
#define reg register
#define int long long
inline bool cmax(reg int &x,reg int y){return x<y?x=y,1:0;}
const int N=5e5+10,INF=1e18;
int n,a[N],b[N],pre[N];
#undef int
std::vector<int> testset(std::vector<int> A, std::vector<int> B, std::vector<int> L, std::vector<int> U){
	std::vector<int> res;
	#define int long long
	n=A.size(); for (reg int i=1;i<=n;i++) a[i]=A[i-1],i<n?b[i]=B[i-1]:0;
	for (reg int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i]+b[i];
	for (reg int i=0;i<L.size();i++){
		reg int pl=0,pr=1e9,ans;
		auto check=[&](reg int x)->bool {
			for (reg int j=L[i]+1,mx=pre[j-1]-b[j-1]-(j-1)*x;j<=U[i]+1;j++){
				reg int now=pre[j]-j*x;
				if (mx>now) return 0; cmax(mx,now-b[j]);
			}
			return 1;
		};
		while (pl<=pr){
			reg int mid=pl+pr>>1;
			if (check(mid)) pl=mid+1,ans=mid; else pr=mid-1;
		}
		res.push_back(ans);
	}
	return res;
}