Sequence and Queries 10

Time limit2sMemory limit512 MB

Summary

For each query with ranges [x1,y1] and [x2,y2], find the maximum subarray sum A_i+...+A_j where i is in the first range and j is in the second.

Level: Hard8 of 10
Topics: Segment tree, Prefix sum, Divide and conquer
Solved: No attempts yet

Problem

You are given a sequence $A_1, A_2, \dots, A_N$ of length $N$ . Write a program that answers the following query.

x1 y1 x2 y2: print the maximum value of $A_i + A_{i+1} + \dots + A_j$ over all pairs $(i, j)$ with $x_1 \le i \le y_1$ , $x_2 \le j \le y_2$ , and $i \le j$ .

Every query in the input satisfies $1 \le x_1 \le x_2 \le N$ , $1 \le y_1 \le y_2 \le N$ , $x_1 \le y_1$ , and $x_2 \le y_2$ , so at least one pair $(i, j)$ always exists.

Input

The first line contains the length of the sequence $N$ ( $1 \le N \le 100{,}000$ ).

The second line contains $A_1, A_2, \dots, A_N$ separated by spaces. ( $-100{,}000 \le A_i \le 100{,}000$ )

The third line contains the number of queries $M$ ( $1 \le M \le 100{,}000$ ).

Each of the next $M$ lines contains one query as four integers $x_1$ , $y_1$ , $x_2$ , $y_2$ , in that order.

Output

Print the answer to each query on its own line.

Examples4

Example 1
Input
```
6
3 -2 1 -4 5 2
2
1 1 2 3
1 3 2 5
```
Expected output
```
2
3
```
Example 2
Input
```
1
1
1
1 1 1 1
```
Expected output
```
1
```

Example 3

Input

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

Expected output

-5
-1
-4
-1
-5

Example 4

Input

9
4 -1 3 -100 -100 -100 2 -1 5
5
1 3 7 9
1 1 9 9
1 2 8 9
3 3 4 4
1 4 5 9

Expected output

-288
-288
-288
-97
-194