#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define int long long
#define L (x<<1)
#define R (x<<1|1)
#define mid ((l+r)>>1)
struct XDS{
	int l,r,lmax,rmax,amax,sum;
}xds[MAXN<<2];
int T,n,a[MAXN],Q;
inline void pushup(int x){
	xds[x].lmax=max(xds[L].lmax,xds[R].lmax+xds[L].sum);
	xds[x].rmax=max(xds[R].rmax,xds[L].rmax+xds[R].sum);
	xds[x].amax=max(max(xds[L].amax,xds[R].amax),xds[L].rmax+xds[R].lmax);
	xds[x].sum=xds[L].sum+xds[R].sum;
	return;
}
inline void build(int x,int l,int r){
	xds[x].l=l;xds[x].r=r;
	if(l==r){
		xds[x].lmax=xds[x].rmax=xds[x].amax=xds[x].sum=a[l];
		return;
	}
	build(L,l,mid);build(R,mid+1,r);
	pushup(x);
	return;
}
inline XDS query(int x,int l,int r){
	if(l>r) return xds[0];
	if(xds[x].l>=l&&xds[x].r<=r) return xds[x];
	if(xds[x].l>r||xds[x].r<l) return xds[0];
	XDS q1=query(L,l,r),q2=query(R,l,r),q3;
	if(q1.l==0) return q2;
	if(q2.l==0) return q1;
	q3.l=q1.l,q3.r=q2.r;
	q3.amax=max(max(q1.amax,q2.amax),q1.rmax+q2.lmax);
	q3.rmax=max(q1.rmax+q2.sum,q2.rmax);
	q3.lmax=max(q1.lmax,q2.lmax+q1.sum);
	q3.sum=q1.sum+q2.sum;
	return q3;
}
signed main(){
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i];
		build(1,1,n);
		cin>>Q;
		while(Q--){
			int l1,r1,l2,r2;
			cin>>l1>>r1>>l2>>r2;
			if(r1==l2) printf("%lld\n",query(1,l1,r1-1).rmax+query(1,l2,r2).lmax);
			else if(r1<l2) printf("%lld\n",query(1,l1,r1).rmax+query(1,l2,r2).lmax+query(1,r1+1,l2-1).sum);
			else printf("%lld\n",max(query(1,l1,l2-1).rmax+query(1,l2,r2).lmax,query(1,l2,r1).amax));
		}
	}
	return 0;
}