rt.

#include <bits/stdc++.h>
using namespace std;
int t,n,m,a[10001],l1,l2,r1,r2;
inline int ls(int p){return p<<1;}
inline int rs(int p){return p<<1|1;}
struct _{
	int maxl,maxr,sum,maxn;
}sg[40001],ans;
_ operator+(_ s,_ x){ 
	_ ans;
	ans.sum=s.sum+x.sum;
	ans.maxl=max(s.maxl,s.sum+x.maxl);
	ans.maxr=max(x.maxr,x.sum+s.maxr);
	ans.maxn=max(s.maxr+x.maxl,max(s.maxn,x.maxn));
	return ans;
}
inline void build(int p,int l,int r){
	if(l==r){
		sg[p].sum=sg[p].maxl=sg[p].maxr=sg[p].maxn=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	sg[p]=sg[ls(p)]+sg[rs(p)];
}
inline _ query(int p,int l,int r,int x,int y){
	if(x<=l&&r<=y)return sg[p];
	int mid=l+r>>1;
	if(x<=mid&&y>mid)return query(ls(p),l,mid,x,y)+query(rs(p),mid+1,r,x,y);
	if(x<=mid)return query(ls(p),l,mid,x,y);
	else return query(rs(p),mid+1,r,x,y);
}
inline int sum(int p,int l,int r,int x,int y){
	if(y>x)return 0;
	if(x<=l&&r<=y)return sg[p].sum;
	int mid=l+r>>1,ans=0;
	if(x<=mid)ans+=sum(ls(p),l,mid,x,y);
	if(y>mid)ans+=sum(rs(p),mid+1,r,x,y);
	return ans;
}
signed main(){
	scanf("%d",&t);
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		build(1,1,n);
		cin>>m;
		for(int i=1;i<=m;i++){
			scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
			if(r1<l2)printf("%d\n",query(1,1,n,l1,r1).maxr+sum(1,1,n,r1+1,l2-1)+query(1,1,n,l2,r2).maxl);
			else{
				int ans=query(1,1,n,l2,r1).maxn;
				if(l2-1>=l1)ans=max(ans,query(1,1,n,l1,l2-1).maxr+query(1,1,n,l2,r2).maxl);
				if(r1+1<=r2)ans=max(ans,query(1,1,n,r1+1,r2).maxl+query(1,1,n,l1,r1).maxr);
				printf("%d\n",ans);
			}
		}
	}
}