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