#include<bits/stdc++.h>
#define inf 1ll<<60
#define int long long
#define SI static inline
using namespace std;
const int N=100005;
int T,n,m,a[N];
struct SegTree{
	int l,r,maxl,maxr,sum,ans;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define maxl(x) tree[x].maxl
	#define maxr(x) tree[x].maxr
	#define sum(x) tree[x].sum
	#define ans(x) tree[x].ans
	SegTree(int L=-inf,int R=-inf,int MAXL=-inf,int MAXR=-inf,int SUM=-inf,int ANS=-inf){
		l=L,r=R,maxl=MAXL,maxr=MAXR,sum=SUM,ans=ANS;
	}
}tree[N<<2];
SI void upd(int x){
	maxl(x)=max(maxl(x<<1),sum(x<<1)+maxl(x<<1|1));
	maxr(x)=max(maxr(x<<1|1),sum(x<<1|1)+maxr(x<<1));
	sum(x)=sum(x<<1)+sum(x<<1|1);
	ans(x)=max(max(ans(x<<1),ans(x<<1|1)),maxr(x<<1)+maxl(x<<1|1));
}
SI void build(int x,int l,int r){
	if(l>r)return;
	if(l==r){
		l(x)=r(x)=l;
		maxl(x)=maxr(x)=sum(x)=ans(x)=a[l];
		return;
	}
	int mid=l+r>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	l(x)=l,r(x)=r,upd(x); 
}
SI SegTree query(int x,int askl,int askr){
	if(askl>askr)return SegTree(0,0,0,0,0,0);
	int l=l(x),r=r(x);
	if(askl<=l&&r<=askr)return tree[x];
	int mid=l+r>>1;
	if(askr<=mid)return query(x<<1,askl,askr);
	if(mid<askl)return query(x<<1|1,askl,askr);
	SegTree ret;
	SegTree lx=query(x<<1,askl,askr);
	SegTree rx=query(x<<1|1,askl,askr);
	ret.maxl=max(lx.maxl,lx.sum+rx.maxl);
	ret.maxr=max(rx.maxr,rx.sum+lx.maxr);
	ret.ans=max(max(lx.ans,rx.ans),lx.maxr+rx.maxl);
	return ret;
}
int ask(int l1,int r1,int l2,int r2){
    if(r1<l2){
    	int tmp=query(1,l1,r1).maxr;
    	tmp+=query(1,r1+1,l2-1).sum;
    	tmp+=query(1,l2,r2).maxl;
    	return tmp;
	}
    int ans=query(1,l2,r1).ans;
    if(l1<l2)ans=max(ans,query(1,l1,l2).maxr+query(1,l2,r2).maxl-a[l2]);
    if(r2>r1)ans=max(ans,query(1,l1,r1).maxr+query(1,r1,r2).maxl-a[r1]);
    return ans;
}
SI void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	cin>>m;
	for(int i=1,l1,r1,l2,r2;i<=m;i++){
		cin>>l1>>r1>>l2>>r2;
		cout<<ask(l1,r1,l2,r2)<<endl;
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--)solve();
}