Largest Sum Subarray

You are given an array of integers. Your task is to find a contiguous subarray (containing at least one number) which has the largest sum, and output its 1-indexed starting and ending positions.

If there are multiple subarrays yielding the same maximum sum, choose the subarray with the smallest starting index. If there is still a tie, choose the one with the smallest ending index.

The optimal solution can be obtained using a modified version of Kadane's algorithm. Mathematically, if you denote the subarray from index i to j (1-indexed) as S(i,j)=\sum_{k=i}^{j}{a_k}, then find indices i and j such that:

$$ \max_{1 \le i \le j \le n} S(i,j) $$

and apply the tie-breaking rules as described.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
N1
a1 a2 ... aN1
N2
a1 a2 ... aN2
... 
NT
a1 a2 ... aNT

Where T is the number of test cases, and for each test case, N is the size of the array followed by N integers separated by spaces.

outputFormat

For each test case, output two integers separated by a space, representing the 1-indexed start and end positions of the subarray with the largest sum. Each result should be printed on a new line on standard output (stdout).

## sample

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

3 4
3 3

</p>