是直接分开维护最大前缀，最大后缀，最大子段，与求和的

#include<bits/stdc++.h>
using namespace std;
#define re register
#define ll long long
#define get getchar()
#define in inline
#define int ll
in int read()
{
	int t=0, x=1; char ch=get;
	while(ch!='-' && (ch<'0' || ch>'9')) ch=get;
	if(ch=='-') ch=get, x=-1;
	while(ch<='9' && ch>='0') t=t*10+ch-'0', ch=get;
	return t*x;
}
const int _=100010;
int a[_],n,m;

#define ls (k<<1)
#define rs (k<<1|1)
int pre[_<<2],suf[_<<2],sx[_<<2],sum[_<<2];
in void pushup(int k)
{
	sx[k]=suf[rs]+pre[ls], pre[k]=max(pre[ls],sum[ls]+pre[rs]);
	suf[k]=max(suf[rs],suf[ls]+sum[rs]), sum[k]=sum[rs]+sum[ls];
} 
in void build(int k,int l,int r)
{
	if(l==r){ pre[k]=suf[k]=sx[k]=sum[k]=a[l]; return ;}
	int mid=l+r>>1;
	build(ls,l,mid), build(rs,mid+1,r);
	pushup(k);
}
in int query_sum(int k,int l,int r,int x,int y)
{
	if(y<x)return 0;
	if(x<=l && r<=y){ return sum[k];}
	int mid=l+r>>1;ll s=0;
	if(x<=mid) s+=query_sum(ls,l,mid,x,y);
	if(y>mid) s+=query_sum(rs,mid+1,r,x,y);
	return s;
}
in int query_suf(int k,int l,int r,int x,int y)
{
	if(y<x) return 0;
	if(x<=l && r<=y) return suf[k];
	int mid=l+r>>1;
	if(y<=mid) return query_suf(ls,l,mid,x,y);
	if(x>mid) return query_suf(rs,mid+1,r,x,y);
	return max(query_suf(ls,l,mid,x,y)+query_sum(rs,mid+1,r,x,y), query_suf(rs,mid+1,r,x,y));
}
in int query_pre(int k,int l,int r,int x,int y)
{
	if(y<x) return 0;
	if(x<=l && r<=y) return pre[k];
	int mid=l+r>>1;
	if(y<=mid){return query_pre(ls,l,mid,x,y);}
	if(x>mid) return query_pre(rs,mid+1,r,x,y);
	return max(query_sum(ls,l,mid,x,y)+query_pre(rs,mid+1,r,x,y), query_pre(ls,l,mid,x,y));
}
in int query_sx(int k,int l,int r,int x,int y)
{
	if(y<x) return 0;
	if(x<=l && r<=y) return sx[k];
	int mid=l+r>>1;
	if(y<=mid){return query_sx(ls,l,mid,x,y);}
	if(x>mid) return query_sx(rs,mid+1,r,x,y);
	return query_suf(ls,l,mid,x,y)+query_pre(rs,mid+1,r,x,y);
}
signed main()
{
	int T=read();
	while(T--)
	{
		memset(sum,0,sizeof(sum));
		memset(suf,0,sizeof(suf));
		memset(pre,0,sizeof(pre));
		memset(sx,0,sizeof(sx));
		n=read();
		for(re int i=1;i<=n;++i) a[i]=read();
		build(1,1,n);
		m=read();
		for(re int i=1;i<=m;++i)
		{
			int l1=read(), r1=read() ,l2=read(), r2=read();
			if(r1<l2) 
				printf("%lld\n", query_suf(1,1,n,l1,r1)+query_sum(1,1,n,r1+1,l2-1)+query_pre(1,1,n,l2,r2));
			else {
				int maxx=query_suf(1,1,n,l1,l2-1)+query_pre(1,1,n,l2,r2);
				maxx=max(maxx,query_suf(1,1,n,l1,r1)+query_pre(1,1,n,r1+1,r2));
				maxx=max(maxx,query_sx(1,1,n,l2,r1));
				printf("%lld\n", maxx);
			}
		}
	}
	return 0;
}