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
computer_argha: 2018-10-24 13:54:40

Though the problem statement states that the size of the array is less than or equal 10000 but test cases have array size more than that so take a larger sized array to solve the problem

tanardi gunawan: 2018-10-03 13:06:30

Last edit: 2018-10-03 13:11:28
shizukaa: 2018-08-05 06:25:33

My first ac in one go!

kishore_p: 2018-07-19 17:23:47

AC in one Go :)
Solve GSS1 first

rkocharyan: 2018-03-20 09:59:57

@alexandro5432 Yes, Abelyan

Last edit: 2018-03-20 10:00:15
alexandro5432: 2018-03-15 15:08:15

shakil0302 y1 is a constant name in library cmath. Thats why you are getting compile errors.

shakil0302: 2017-09-23 08:25:25

Anybody tried 'long long y1' as variable? Costs me 2 compiler error!!

beginner_1998: 2017-09-14 00:02:31

weak test cases
my code gives wa for following input but still got accepted
20 4 -6 1 -8 -9 2 5 -6 -8 -9 -3 5 -4 6 7 3 2 -9 8 -7 3 -5 -6 7 8
5
1 3 6 7
1 2 4 20
1 8 9 10
2 5 6 7
8 12 17 19

shahidul_brur: 2016-11-13 12:21:52

why for the first query (i.e. 1 1 2 3) ans is 2 ?
Can anyone explain, please ?

Last edit: 2016-11-13 12:22:59
Ashwani Gautam: 2016-09-23 01:28:28

no need to use scanf and printf, if you are using the "data structure" neatly ;)


Added by:Frank Rafael Arteaga
Date:2008-08-06
Time limit:0.132s
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.