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

Added by:Frank Rafael Arteaga
Date:2008-08-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:K.-Y. Chen and K.-M. Chao, On the Range Maximum-Sum Segment Query Problem, 2007.

hide comments
2016-09-23 01:28:28 Ashwani Gautam
no need to use scanf and printf, if you are using the "data structure" neatly ;)
2016-08-30 12:01:25
Maximum N for some test cases is greater than 10^4. I was using 10^4 as maximum N but I was getting a SIGSEV. Got AC with 10^5 max N. Please fix either the statement or the test cases. Thanks for the problem!
2016-07-17 09:29:22 Min_25
[ Note ]
Some input file does not end with '\n'.

Last edit: 2016-07-17 09:29:37
2016-02-15 06:33:58 minhthai
very tricky :)
2016-02-10 08:54:08 Vipul
used cin/cout in place of scanf/printf....AC
can't understand how
2015-07-05 05:51:21 Stupid Dog
i > j ????
2015-04-28 15:04:06 Luis Manuel Díaz Barón
Beautiful problem. Solve GSS1 first and then this will be easy
2015-02-08 03:20:55 OIdiot
@Harsh Shah ,of course it can.
In the Example I/O, the 2nd query shows it--- y1=3 and x2=2
2015-01-23 06:20:15 Harsh Shah
can y1 be greater than x2?

Last edit: 2015-01-23 14:19:47
2014-12-04 10:27:52 Rahul
Did GSS1 and GSS3 before. This becomes easy then.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.