Diamond Mining Profits

Interview

Time limit1sMemory limit128 MB

Summary

Find the contiguous period with the largest total gain across up to 2000 test cases, breaking ties by shorter length then earlier start.

Level: Medium4 of 10
Topics: Dynamic programming, Array, Prefix sum
Solved: No attempts yet

Problem

You run a business that mines diamonds from a river. The government lets you lower the machine into the river once, and you have to pull it out before the permit runs out. After you lower it, you may pull it out on any day you choose.

The machine uses a diamond as its drilling head, so running it costs diamonds. Your company owns a precise detector that tells you in advance, for every day from the first day of the permit to the last one, how many diamonds you gain or lose that day.

Write a program that finds the period in which your company earns the most diamonds.

Input

The first line contains the number of test cases $N$ . ( $1 \le N \le 2000$ )

Each of the next $N$ lines contains one test case. A test case consists of $M + 1$ numbers. The first number is the total number of days the government grants, $M$ . ( $1 \le M \le 500$ ) The next $M$ numbers are the predicted gain or loss of diamonds on each day, and every one of them is an integer between $-100$ and $100$ .

Output

Print $N$ lines, one per test case. On each line print the starting day, the ending day, and the largest total profit, in that order. The first day of the input is day 1 and the last one is day $M$ .

If no period gives a positive profit, print 0 0 0. If several periods give the same profit, choose the shorter one, and if their lengths are equal as well, choose the one that starts earlier.

Examples1

Example 1

Input

6
16 4 3 -10 3 -1 2 0 -3 5 7 -4 -8 -10 4 7 -30
6 -1 0 -3 -1 0 -1
10 -1 -4 -5 -9 -14 5 6 7 -10 10
3 -2 -3 -4
17 1 2 3 4 5 6 7 8 9 -10 -11 10 9 8 -7 -6 13
7 1 2 3 -10 3 2 1

Expected output