#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
int s[10010],T,n,m;
struct sss
{
	int l,r,ma,mi,p1,p2;
}t[200001];
struct ss
{
	int pos,siz;
	bool friend operator <(ss x,ss y)
	{
		return x.siz<y.siz;
	}
	bool friend operator >(ss x,ss y)
	{
		return x.siz>y.siz;
	}
};
void up(int x)
{
	if(t[x*2].ma>t[x*2+1].ma)
	{
		t[x].ma=t[x*2].ma;
		t[x].p1=t[x*2].p1;
	}
	else
	{
		t[x].ma=t[x*2+1].ma;
		t[x].p1=t[x*2+1].p1;
	}
	if(t[x*2].mi<t[x*2+1].mi)
	{
		t[x].mi=t[x*2].mi;
		t[x].p2=t[x*2].p2;
	}
	else
	{
		t[x].mi=t[x*2+1].mi;
		t[x].p2=t[x*2+1].p2;
	}
}
void build(int x,int l,int r)
{
	t[x].l=l,t[x].r=r;
	if(l==r)
	{
		t[x].ma=s[l];
		t[x].mi=s[l];
		t[x].p1=t[x].p2=l;
		return ;
	}
	int mid=(l+r)/2;
	build(x*2,l,mid);
	build(x*2+1,mid+1,r);
	up(x);
}
ss query1(int x,int L,int R)
{
	int l=t[x].l,r=t[x].r;
	if(L<=l&&R>=r) return ss{t[x].p1,t[x].ma};	
	int mid=(l+r)/2;
	ss ans={0,-2147483646};
	if(L<=mid) ans=query1(x*2,L,R);
	if(R>mid) ans=max(ans,query1(x*2+1,L,R));
	return ans;
}
ss query2(int x,int L,int R)
{
	int l=t[x].l,r=t[x].r;
	if(L<=l&&R>=r) return ss{t[x].p2,t[x].mi};
	int mid=(l+r)/2;
	ss ans={0,2147483646};
	if(L<=mid) ans=query2(x*2,L,R);
	if(R>mid) ans=min(ans,query2(x*2+1,L,R));
	return ans;
}
signed main()
{
	scanf("%d",&T);
	while(T)
	{
		T-=1;
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&s[i]),s[i]+=s[i-1];
		build(1,0,n);
		scanf("%d",&m);
		for(int i=1;i<=m;i++)
		{
			int x1,y1,x2,y2,ans,anss;
			ss now;
			scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
			if(y1<x2)
			{
				now=query1(1,x2,y2);
	      		ans=now.pos;
	     		now=query2(1,x1-1,y1);
	    		ans=s[ans]-s[now.pos];
			}
			else
			{
				now=query1(1,x2,y2);
				ans=now.pos;
				now=query2(1,x1-1,x2);
				ans=s[ans]-s[now.pos];
				now=query1(1,y1,y2);
				anss=now.pos;
				now=query2(1,x1-1,y1);
				anss=s[anss]-s[now.pos];
				ans=max(ans,anss);
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}

处理的是前缀和，从起点到当前位置的前缀和，然后求左端点的前缀和的最小值，右端点的最大值，然后相减，应该没错，如果算法出错求巨佬hack

救命救命救命