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
theshumo: 2024-02-17 07:01:25

1
8
-5 2 -5 5 3 6 2 4
3
4 8 5 6
4 6 6 6
2 3 5 5
how this example
why dont 14 14 5

abhi_8: 2023-08-12 08:50:31

You can solve it, all the best!

alphazero56: 2022-08-18 12:35:34

Good extension of GSS1

mindeveloped: 2022-08-08 14:39:02

This problem is Dless

canhnam357: 2021-12-23 06:51:13

subarray with at least one element so sum maybe negative :")

Abhishek Jaisingh: 2021-05-10 15:12:49

AC after multiple attempts. Great brain exercise nevertheless. ;)
GSS1 + tweak + edge-cases = GSS5

Last edit: 2021-05-10 15:13:51
varunsainii: 2020-05-20 17:57:10

AC in one go. But great brain exercise.

zakir068: 2020-02-25 09:44:41

Copied the Gss1 code + some implementation

hvh2911: 2019-10-08 11:24:13

One HIT AC :V :V

scorpy1: 2019-09-13 04:52:55

AC in 1 GO!


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.