Description:

Solution:

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int testcases = 0;

int n,m;

#define MAXN 10010

int a[MAXN];

int sum[MAXN];

struct node

{

	int lc,rc;

	int ls,rs,ms,s;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

void merge(node &rt,node lc,node rc)

{

	rt.ls = max(lc.ls,lc.s + rc.ls);

	rt.rs = max(rc.rs,rc.s + lc.rs);

	rt.s = lc.s + rc.s;

	rt.ms = max(max(lc.ms,rc.ms),lc.rs + rc.ls);

	return;

}

void build(int rt,int l,int r)

{

	if(l == r)

	{

		t[rt].s = t[rt].ms = t[rt].ls = t[rt].rs = a[l];

		return;

	}

	int mid = ((l + r) >> 1);

	build(t[rt].lc = newnode(),l,mid);

	build(t[rt].rc = newnode(),mid + 1,r);

	merge(t[rt],t[t[rt].lc],t[t[rt].rc]);

	return;

}

node query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)

	{

		return t[rt];

	}

	int mid = ((l + r) >> 1);

	if(R <= mid)return query(t[rt].lc,L,R,l,mid);

	if(L >= mid + 1)return query(t[rt].rc,L,R,mid + 1,r);

	node res;

	merge(res,query(t[rt].lc,L,R,l,mid),query(t[rt].rc,L,R,mid + 1,r));

	return res;

}

void work()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&a[i]);

		sum[i] = sum[i - 1] + a[i];

	}

	ptr = 0;

	memset(t,0,sizeof(t));

	build(root = newnode(),1,n);

	scanf("%d",&m);

	int x1,y1,x2,y2;

	int res;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

		res = 0;

		if(y1 + 1 < x2)

		{

			res = query(root,x1,y1,1,n).rs + sum[x2 - 1] - sum[y1] + query(root,x2,y2,1,n).ls;

		}

		if(y1 + 1 == x2)

		{

			res = query(root,x1,y1,1,n).rs + query(root,x2,y2,1,n).ls;

		}

		if(x2 == y1)

		{

			res = max(a[x2],query(root,x1,y1,1,n).rs + query(root,x2,y2,1,n).ls - a[x2]);

		}

		if(y1 - 1 == x2)

		{

			node le = query(root,x1,x2,1,n),ri = query(root,y1,y2,1,n);

			res = max(max(le.rs,ri.ls),le.rs + ri.ls);

		}

		if(y1 - 1 > x2)

		{

			int mid = sum[y1 - 1] - sum[x2];

			node le = query(root,x1,x2,1,n),ri = query(root,y1,y2,1,n),mi = query(root,x2 + 1,y1 - 1,1,n);

			res = max(max(le.rs + mid + ri.ls,mi.ms),max(le.rs + mi.ls,mi.rs + ri.ls));

			res = max(res,max(le.rs,ri.ls));

		}

		printf("%d\n",res);

	}

	

	

	return;

}

int main()

{

	scanf("%d",&testcases);

	for(int i = 1;i <= testcases;++i)

	{

		work();

	}

	return 0;

}