#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e4+5;
#define lid (id << 1)
#define rid (id << 1 | 1)
struct node{
	int l, r;
	ll ans, sum, lmax, rmax;
};
node tr[N << 2];
int n, q;
int a[N];
void pushup(node &t, node ls, node rs){
	if(ls.rmax < 0 && rs.lmax < 0)
		t.ans=max(ls.rmax, rs.lmax);
	else{
		t.ans = 0;
		if(ls.rmax>0) t.ans += ls.rmax;
		if(rs.lmax>0) t.ans += rs.lmax;
	}
	t.sum = ls.sum + rs.sum;
	t.lmax = max(ls.lmax, ls.sum + rs.lmax);
	t.rmax = max(rs.rmax, rs.sum + ls.rmax);
	t.ans = max(max(ls.ans, rs.ans), ls.rmax + rs.lmax);
}
void build(int id, int l, int r){
	tr[id].l = l;
	tr[id].r = r;
	if (l == r){
		tr[id].sum = tr[id].ans = tr[id].lmax = tr[id].rmax = a[l];
		return;
	}
	int mid = (tr[id].l + tr[id].r) / 2;
	build(lid, l, mid);
	build(rid, mid + 1, r);
	pushup(tr[id], tr[lid], tr[rid]);
}
node query(int id, int l, int r){
	if (l > r) return (node){0, 0, 0, 0, 0, 0};
	if (l <= tr[id].l && tr[id].r <= r){
		return tr[id];
	}
	int mid = (tr[id].l + tr[id].r) / 2;
	if (r <= mid) return query(lid, l, r);
	else if (l > mid) return query(rid, l, r);
	node t;
	pushup(t, query(lid, l, mid), query(rid, mid + 1, r));
	return t;
}
int main(){ 
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin >> T;
	while (T--){
		cin >> n;
		for (int i = 1;i <= n;i++){
			cin >> a[i];
		}
		memset(tr, 0, sizeof tr);
		build(1, 1, n);
		
		cin >> q;
		while (q--){
			int l1, r1, l2, r2;
			cin >> l1 >> r1 >> l2 >> r2;
			if (l2 > r1){
				//cout << 1;
				cout << query(1, l1, r1).rmax + query(1, r1, l2).sum + query(1, l2, r2).lmax - a[r1] - a[l2] << '\n';
			}
			else{
				ll ans = query(1, l2, r1).sum;
				if (l1 < l2) ans = max(ans, query(1, l1, l2).rmax + query(1, l2, r2).lmax - a[l2]);
				if (r2 > r1) ans = max(ans, query(1, l1, r1).rmax + query(1, r1, r2).lmax - a[r1]);
				cout << ans << '\n';
			}
		}
	}
	return 0;
}