Rt，能给我一组hack数据也行。

#include <bits/stdc++.h>
//#define int long long
const int Maxn = 1e5 + 10; 

int T; 
int n, m;
int val[Maxn];  

struct node {
	int sum; 
	int maxl, maxr; 
	int max_; 
} tree[Maxn << 2], Null;

int read() {
	int sum = 0, flag = 1; char ch = getchar(); 
	for (; (ch < '0' || ch > '9') && ch != '-'; ch = getchar()); 
	if (ch == '-') flag = -1, ch = getchar(); 
	for (; ch >= '0' && ch <= '9'; ch = getchar())
		sum = sum * 10 + ch - '0'; 
	return sum * flag; 
}

inline int lson(int x) {
	return x << 1; 
}

inline int rson(int x) {
	return x << 1 | 1; 
}

void push_up(int x) {
	tree[x].sum = tree[lson(x)].sum + tree[rson(x)].sum; 
	tree[x].maxl = std::max(tree[lson(x)].maxl, tree[lson(x)].sum + tree[rson(x)].maxl); 
	tree[x].maxr = std::max(tree[rson(x)].maxr, tree[rson(x)].sum + tree[lson(x)].maxr); 
	tree[x].max_ = std::max(std::max(tree[lson(x)].max_, tree[rson(x)].max_), tree[lson(x)].maxr + tree[rson(x)].maxl); 
}

void build(int now, int l, int r) {
	if (l > r) return; 
	if (l == r) {
		tree[now].sum = tree[now].maxl = tree[now].maxr = tree[now].max_ = val[l]; 
		return; 
	}
	int mid = l + r >> 1; 
	build(lson(now), l, mid); 
	build(rson(now), mid + 1, r); 
	push_up(now); 
}

node query(int now, int l, int r, int L, int R) {
	int mid = l + r >> 1; 
	if (L > R) return Null; 
	if (L <= l && r <= R) 
		return tree[now]; 
	else if (R <= mid)
		return query(lson(now), l, mid, L, R); 
	else if (mid < L)
		return query(rson(now), mid + 1, r, L, R); 
	else {
		node a, b, ans; 
		a = query(lson(now), l, mid, L, R); 
		b = query(rson(now), mid + 1, r, L, R); 
		ans.sum = a.sum + b.sum; 
		ans.maxl = std::max(a.maxl, a.sum + b.maxl); 
		ans.maxr = std::max(b.maxr, b.sum + a.maxr); 
		ans.max_ = std::max(std::max(a.max_, b.max_), a.maxr + b.maxl); 
		return ans; 
	}
}

signed main() {
	int i, j; 
	T = read(); 
	Null.sum = Null.maxl = Null.maxr = Null.max_ = 0; 
	while (T--) {
		n = read(); 
//		memset(tree, -0x3f, sizeof(tree)); 
		for (i = 1; i <= n; i++) {
			val[i] = read(); 
		}
		build(1, 1, n); 
		m = read(); 
		for (i = 1; i <= m; i++) {
			int x1, y1, x2, y2; 
			x1 = read(), y1 = read(), x2 = read(), y2 = read(); 
			if (y1 < x2) {
				printf("%d\n", query(1, 1, n, x1, y1 - 1).maxr 
				+ query(1, 1, n, y1, x2).sum 
				+ query(1, 1, n, x2 + 1, y2).maxl); 
			}
			else if (y2 < x1) {
				printf("0\n"); 
			}
			else if (x1 <= x2 && x2 <= y1 && y1 <= y2) {
				printf("%d\n", std::max(std::max(
				query(1, 1, n, x1, x2 - 1).maxr 
				+ query(1, 1, n, x2, y1).sum 
				+ query(1, 1, n, y1 + 1, y2).maxl, 
				query(1, 1, n, x2, y1).max_), 
				std::max(
				query(1, 1, n, x1, x2 - 1).maxr 
				+ query(1, 1, n, x2, y1).maxl, 
				query(1, 1, n, x2, y1 - 1).maxr
				+ query(1, 1, n, y1, y2).maxl))); 
			}
			else if (x2 <= x1 && x1 <= y2 && y2 <= y1) {
				printf("%d\n", std::max(std::max(
				query(1, 1, n, x2, x1 - 1).maxr 
				+ query(1, 1, n, x1, y2).sum 
				+ query(1, 1, n, y2 + 1, y1).maxl, 
				query(1, 1, n, x1, y2).max_), 
				std::max(query(1, 1, n, x2, x1 - 1).maxr 
				+ query(1, 1, n, x1, y2).maxl, 
				query(1, 1, n, x1, y2 - 1).maxr
				+ query(1, 1, n, y2, y1).maxl))); 
			}
			else if (x1 <= x2 && y2 <= y1) {
				printf("%d\n", std::max(query(1, 1, n, x2, y2).max_, 
				query(1, 1, n, x1, x2 - 1).maxr + query(1, 1, n, x2, y2).maxl)); 
			}
			else if (x2 <= x1 && y1 <= y2) {
				printf("%d\n", std::max(query(1, 1, n, x1, y1).max_, 
				query(1, 1, n, x1, y1 - 1).maxr + query(1, 1, n, y1, y2).maxl)); 
			}
		}
	}
	return 0; 
}