GSS5  Can you answer these queries V
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.
Input
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.
Output
Your program should output the results of the M queries for each test case, one query per line.
Example
Input: 2 6 3 2 1 4 5 2 2 1 1 2 3 1 3 2 5 1 1 1 1 1 1 1 Output: 2 3 1
hide comments
Min_25:
20160717 09:29:22
[ Note ]


minhthai:
20160215 06:33:58
very tricky :) 

Vipul:
20160210 08:54:08
used cin/cout in place of scanf/printf....AC


Stupid Dog:
20150705 05:51:21
i > j ???? 

Luis Manuel Díaz Barón:
20150428 15:04:06
Beautiful problem. Solve GSS1 first and then this will be easy 

OIdiot:
20150208 03:20:55
@Harsh Shah ,of course it can.


Harsh Shah:
20150123 06:20:15
can y1 be greater than x2? Last edit: 20150123 14:19:47 

Rahul:
20141204 10:27:52
Did GSS1 and GSS3 before. This becomes easy then. 

Mostafa 36a2:
20140829 19:18:03
@EB or @PS : please fix the statement on

Added by:  Frank Rafael Arteaga 
Date:  20080806 
Time limit:  0.132s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 strict ERL JS NODEJS PERL 6 VB.net 
Resource:  K.Y. Chen and K.M. Chao, On the Range MaximumSum Segment Query Problem, 2007. 