#include<bits/stdc++.h>
#define mid (tl + tr) / 2
#define ll i << 1
#define rr (i << 1) + 1
using namespace std;
const int MAXN = 100000;
int n,a[MAXN],sum[MAXN];
struct node{
	int lmx,rmx,sum,sumax;
}tree[MAXN];
void build(int i,int tl,int tr){
	if(tl == tr){
		tree[i].lmx = tree[i].rmx = tree[i].sum = tree[i].sumax = a[tl];
		return;
	}
	build(ll,tl,mid);
	build(rr,mid + 1,tr);
	tree[i].lmx = max(tree[ll].lmx,tree[ll].sum + tree[rr].lmx);
	tree[i].rmx = max(tree[rr].rmx,tree[rr].sum + tree[ll].rmx);
	tree[i].sum = tree[ll].sum + tree[rr].sum;
	tree[i].sumax = max(max(tree[ll].sumax,tree[rr].sumax),tree[ll].rmx + tree[rr].lmx);
}
int m,x11,y11,x22,y22;
node query(int i,int tl,int tr,int l,int r){//查找某区间里从左端点开始的最大值，从右断电开始的最大值，区间中和最大值，区间和 
	node ans = {0,0,0},a,b;
	if(l > r)return ans;
	if(tl == l && tr == r || tl == tr)return tree[i];
	if(r <= mid)return query(ll,tl,mid,l,r);
	else if(l >= mid)return query(rr,mid + 1,tr,l,r);
	else if(l < mid && r > mid){
		a = query(ll,tl,mid,l,min(r,mid));
		b = query(rr,mid + 1,tr,max(l,mid + 1),r);
		ans.sum = a.sum + b.sum;
		ans.sumax = max(max(a.sumax,b.sumax),a.rmx + b.lmx);
		ans.lmx = max(a.lmx,a.sum + b.lmx);
		ans.rmx = max(b.rmx,b.sum + a.rmx);
		return ans;
	}
}
int t;
node now; 
int main(){
	cin >> t;
	while(t--){
		cin >> n;
		memset(a,0,sizeof a);
		memset(tree,0,sizeof tree);
		for(int i = 1; i <= n;i++){
			cin >> a[i];
			sum[i] = sum[i - 1] + a[i];
		}
		build(1,1,n);
		cin >> m;
		for(int i = 1; i <= m; i++){
			cin >> x11 >> y11 >> x22 >> y22;
			if(x11 > x22){
				swap(y11,y22);
				swap(x11,x22);
			}
			if(y11 < x22){//区间相分隔 
				cout << query(1,1,n,x11,y11).rmx + sum[x22] - sum[y11] + query(1,1,n,x22 + 1,y22).lmx << "\n";
			} 
			else if(y11 == x22)cout << query(1,1,n,x11,y11).rmx + query(1,1,n,x22 + 1,y22).lmx << "\n";//左区间右端点为右区间左端点 
			else if(y11 > x22 && x22 > x11){//区间重合 
				int k = max(query(1,1,n,x22,y11).sumax,sum[y11] - sum[x22 - 1] + query(1,1,n,y11 + 1,y22).lmx + query(1,1,n,x11,x22 - 1).rmx);
				k = max(k,max(query(1,1,n,x11,x22).rmx + query(1,1,n,x22 + 1,y22).lmx,query(1,1,n,y11,y22).lmx + query(1,1,n,x22,y11 - 1).rmx));
				cout << k << "\n";
			}
			else if(x11 <= x22 && y22 <= y11){//区间相包含 
				cout << max(query(1,1,n,x22,y22).sumax,max(query(1,1,n,x22,y22).lmx + query(1,1,n,x11,x22 - 1).rmx,query(1,1,n,y22,y11).rmx + query(1,1,n,x22,y22 - 1).rmx)) << "\n";
			}
		}
	}
	return 0;
}