GSS5 - Can you answer these queries V

给定一个序列。查询左端点在$[x_1, y_1]$之间，且右端点在$[x_2, y_2]$之间的最大子段和，数据保证$x_1\leq x_2,y_1\leq y_2$​ ，但是不保证端点所在的区间不重合 感谢@Anoxiacxy 提供的翻译

You are given a sequence A\[1\], A\[2\], ..., A\[N\] . ( |A\[i\]| <= 10000 , 1 <= N <= 10000 ). A query is defined as follows: Query(x1,y1,x2,y2) = Max { A\[i\]+A\[i+1\]+...+A\[j\] ; x1 <= i <= y1 , x2 <= j <= y2 and x1 <= x2 , y1 <= y2 }. Given M queries (1 <= M <= 10000), your program must output the results of these queries.

The first line of the input consist of the number of tests cases <= 5. Each case consist of the integer N and the sequence A. Then the integer M. M lines follow, contains 4 numbers x1, y1, x2 y2.

Your program should output the results of the M queries for each test case, one query per line.

2
6 3 -2 1 -4 5 2
2
1 1 2 3
1 3 2 5
1 1
1
1 1 1 1

2
3
1