#include<bits/stdc++.h>
#define int long long
#define zd (p<<1)
#define yd (p<<1|1)	
using namespace std;
const int INF=-1e9;
int read();
void write(int x);
struct node{
	int num,lmx,rmx,ans,l,r;
}tr[200001];
int dat[50001],n,m,a,b,c,d,t;
void pushup(int p);
void build(int p,int l,int r);
node query(int p,int l,int r,int ql,int qr);
int ansss(int l1,int r1,int l2,int r2);
signed main(){
	t=read();
	while(t--){
		n=read();
		build(1,1,n);
		m=read();
		while(m--){
			a=read(),b=read(),c=read(),d=read();
			write(ansss(a,b,c,d));
			printf("\n");
		}
	}
	return 0;
} 
int read() {
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
void write(int x) {
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}
void pushup(int p){
	tr[p].num=tr[zd].num+tr[yd].num;
	tr[p].lmx=max(tr[zd].lmx,tr[zd].num+tr[yd].lmx);
	tr[p].rmx=max(tr[yd].rmx,tr[yd].num+tr[zd].rmx);
	tr[p].ans=max(tr[zd].ans,max(tr[yd].ans,tr[zd].rmx+tr[yd].lmx));
}
void build(int p,int l,int r){
//	cout<<l<<" "<<r<<"\n\n";
	tr[p].l=l;
	tr[p].r=r;
	if(l==r){
		dat[l]=read(); 
		tr[p].num=tr[p].ans=tr[p].lmx=tr[p].rmx=dat[l];
//		cout<<a[l]<<" "<<l<<"\n";
		return;
	} 
	int mid=(l+r)/2;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	pushup(p);
}
node query(int p,int l,int r,int ql,int qr){
	if(ql>r||qr<l)return {0,0,0,0,0};
	if(ql<=l&&qr>=r) return tr[p];
	int mid=(l+r)>>1;
	node x=query(zd,l,mid,ql,qr);
	node y=query(yd,mid+1,r,ql,qr);
	node z;
	z.num=x.num+y.num;
	z.lmx=max(x.lmx,x.num+y.lmx);
	z.rmx=max(y.rmx,y.num+x.rmx);
	z.ans=max(x.ans,max(y.ans,x.rmx+y.lmx));
	return z;
} 
int ansss(int l1,int r1,int l2,int r2){
    if(r1<l2){
        int tmp=query(1,1,n,l1,r1).rmx;
        tmp+=query(1,1,n,r1+1,l2-1).num;
        tmp+=query(1,1,n,l2,r2).lmx;
        return tmp;
    }
    int ans=query(1,1,n,l2,r1).ans;
    if(l1<l2)ans=max(ans,query(1,1,n,l1,l2).rmx+query(1,1,n,l2,r2).lmx-dat[l2]);
    if(r2>r1)ans=max(ans,query(1,1,n,l1,r1).rmx+query(1,1,n,r1,r2).lmx-dat[r1]);
    ans=max(ans,0ll);
    return ans;
}