rt，但是不想让大家帮我调（调出来了说也没事）

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct FenKuai{
	int ll[6500],sum[6500],PreMaxSum[6500],PosMaxSum[6500],MaxAns[6500],Max[6500];
	int id[500005],a[500005];
	void MakeMax(int &x,int y)
	{
		x=(x>y?x:y);
	}
	void build(int n)
	{
		int kc,PreSum,PosSum,PreMax,tot=0;
		kc=sqrt(n);
		memset(ll,0,sizeof(ll));
		memset(sum,0,sizeof(sum));
		memset(PreMaxSum,0,sizeof(PreMaxSum));
		memset(PosMaxSum,0,sizeof(PosMaxSum));
		memset(MaxAns,0,sizeof(MaxAns));
		memset(Max,0,sizeof(Max));
		memset(id,0,sizeof(id));
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			id[i]=(i-1)/kc+1;
			int I=id[i];
			sum[I]+=a[i];
			if(I!=id[i-1])
			{
				ll[++tot]=i;
				PreSum=0;
				PreMax=0;
				Max[I]=INT_MIN;
				PreMaxSum[I]=0;
				MaxAns[I]=0;
			}
			Max[I]=max(Max[I],a[i]);
			PreSum+=a[i];
			MakeMax(PreMaxSum[I],PreSum);
			MakeMax(MaxAns[I],PreMax=max(PreMax+a[i],0ll));
		}
		ll[tot+1]=n+1;
		for(int i=n;i>=1;i--)
		{
			if(id[i]!=id[i+1]) PosSum=0,PosMaxSum[id[i]]=0;
			PosSum+=a[i];
			MakeMax(PosMaxSum[id[i]],PosSum);
		}
	}
	void update(int l,int k)
	{
//		if(l>r) return 0;
		int L=id[l];
		Max[L]=INT_MIN;
		PreMaxSum[L]=0;
		MaxAns[L]=0;
		PosMaxSum[L]=0;
		a[l]=k;
		int PreSum=0,PosSum=0,PreMax=0;
		for(int i=ll[L];i<ll[L+1];i++)
		{
			sum[L]+=a[i];
			PreSum+=a[i];
			Max[L]=max(Max[L],a[i]);
			MakeMax(PreMaxSum[L],PreSum);
			PreMax=max(PreMax+a[i],0ll);
			MakeMax(MaxAns[L],PreMax);
		}
		for(int i=ll[L+1]-1;i>=ll[L];i--)
		{
			PosSum+=a[i];
			MakeMax(PosMaxSum[L],PosSum);
		}
	}
	int querySMax(int now,int l,int r)
	{
		if(l>r) return 0;
		int ans=0;
		for(int i=l;i<=r;i++)
		{
			now=max(now,0ll)+a[i];
			MakeMax(ans,now);
		}
		return ans;
	}
	int queryMax(int l,int r)
	{
		if(l>r) return 0;
		int L=id[l],R=id[r];
		if(L==R)
		{
			int ans=INT_MIN;
			for(int i=l;i<=r;i++) ans=max(ans,a[i]);
			if(ans<0) return ans;
			else return querySMax(0,l,r);
		}
		else
		{
			int ans=0,now=0,MAX=INT_MIN;
			for(int i=l;i<ll[L+1];i++)
			{
				now=max(now,0ll)+a[i];
				MakeMax(ans,now);
				MAX=max(MAX,a[i]);
			}
			for(int i=L+1;i<R;i++)
			{
				MakeMax(ans,now);
				MakeMax(ans,now+PreMaxSum[i]);
				MakeMax(ans,MaxAns[i]);
				now=max(now+sum[i],PosMaxSum[i]);
				MAX=max(MAX,Max[i]);
			}
			MakeMax(ans,now);
			for(int i=ll[R];i<=r;i++) MAX=max(MAX,a[i]);
			if(MAX<0) return MAX;
			else return max(ans,querySMax(now,ll[R],r));
		}
	}
	int query_Pre(int l,int r)
	{
		if(l>r) return 0;
		int L=id[l],R=id[r];
		if(L==R)
		{
			int Pre=0,MaxPre=INT_MIN;
			for(int i=l;i<=r;i++)
			{
				Pre+=a[i];
				MaxPre=max(Pre,MaxPre);
			}
			return MaxPre;
		}
		else
		{
			int Pre=0,MaxPre=INT_MIN;
			for(int i=l;i<ll[L+1];i++)
			{
				Pre+=a[i];
				MaxPre=max(Pre,MaxPre);
			}
			for(int i=L+1;i<R;i++)
			{
				MaxPre=max(MaxPre,Pre+PreMaxSum[i]);
				Pre+=sum[i];
				MaxPre=max(MaxPre,Pre);
			}
			for(int i=ll[R];i<=r;i++)
			{
				Pre+=a[i];
				MaxPre=max(Pre,MaxPre);
			}
			return MaxPre;
		}
	}
	int query_Pos(int l,int r)
	{
		if(l>r) return 0;
		int L=id[l],R=id[r];
		if(L==R)
		{
			int Pos=0,MaxPos=INT_MIN;
			for(int i=r;i>=l;i--)
			{
				Pos+=a[i];
				MaxPos=max(Pos,MaxPos);
			}
			return MaxPos;
		}
		else
		{
			int Pos=0,MaxPos=INT_MIN;
			for(int i=r;i>=ll[R];i--)
			{
				Pos+=a[i];
				MaxPos=max(Pos,MaxPos);
			}
			for(int i=R-1;i>L;i--)
			{
				MaxPos=max(MaxPos,Pos+PosMaxSum[i]);
				Pos+=sum[i];
				MaxPos=max(MaxPos,Pos);
			}
			for(int i=ll[L+1]-1;i>=l;i--)
			{
				Pos+=a[i];
				MaxPos=max(Pos,MaxPos);
			}
			return MaxPos;
		}
	}
	int query_sum(int l,int r)
	{
		if(l>r) return 0;
		int L=id[l],R=id[r];
		if(L==R)
		{
			int Sum=0;
			for(int i=l;i<=r;i++) Sum+=a[i];
			return Sum;
		}
		else
		{
			int Sum=0;
			for(int i=l;i<ll[L+1];i++)
				Sum+=a[i];
			for(int i=L+1;i<R;i++) Sum+=sum[i];
			for(int i=ll[R];i<=r;i++)
				Sum+=a[i];
			return Sum;
		}
	}
	int query_max(int l,int r)
	{
		if(l>r) return 0;
		
		int L=id[l],R=id[r];
		if(L==R)
		{
			int ans=INT_MIN;
			for(int i=l;i<=r;i++) ans=max(ans,a[i]);
			return ans;
		}
		else
		{
			int ans=0,now=0,MAX=INT_MIN;
			for(int i=l;i<ll[L+1];i++) MAX=max(MAX,a[i]);
			for(int i=L+1;i<R;i++) MAX=max(MAX,Max[i]);
			for(int i=ll[R];i<=r;i++) MAX=max(MAX,a[i]);
			return MAX;
		}
	}
}fk;
signed main()
{
	int n,q,l1,r1,l2,r2,T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		fk.build(n);
		cin>>q;
		while(q--)
		{
			cin>>l1>>r1>>l2>>r2;
			if(l1==l2&&r1==r2) cout<<fk.queryMax(l1,r1)<<'\n';
			else if(r1<=l2)
			{
				cout<<fk.query_Pos(l1,r1)+fk.query_sum(r1+1,l2-1)+fk.query_Pre(l2,r2)<<'\n';
			}
//			else if(r1==l2)
//			{
//				cout<<fk.query_Pos(l1,r1)+fk.query_Pre(l2+1,r2)<<'\n';
//			}
			else 
			{
				int S=fk.queryMax(l2+1,r1-1);
				cout<<max(S,fk.query_Pos(l1,l2)+fk.query_sum(l2+1,r1-1)+fk.query_Pre(r1,r2))<<'\n';
			}
		}
	}
	return 0;
}