Description

{ -1, 2, 5, -3, 9, 8, -4, -5, 10, -11 } 의 수열이 있을 때, 이 수열의 모든 원소의 합을 구하면 10이다.

하지만 2번째 원소부터, 9번째 원소까지의 합을 구하면 22로 이 수열의 경우 2번째부터 9번째까지의 부분수열이 이 수열의 최대 부분수열이 된다.

N개의 원소로 이루어진 수열을 입력받았을 때 이 수열의 부분 수열중 합이 최대가 되는 부분수열을 구하는 프로그램을 작성하라.

 

Input

맨 처음 테스트 케이스의 갯수 T(1 <= T <= 100)를 입력받는다. 그 뒤에 T의 갯수만큼 원소의 개수 N을 입력받고 N개의 원소 e[i]를 입력받는다. (3 <= N <= 500, -1000 <= e[i] <= 1000)

Output

각 테스트 케이스마다 수열의 부분 수열중 합이 최대가 되는 부분수열을 구하여 시작점과 끝점 및 부분수열의 합을 출력한다.

Sample Input3 4 1 -1 1 2 5 1 -2 3 -4 5 10 -1 2 5 -3 9 8 -4 -5 10 -11 Sample Output3 4 3 5 5 5 2 9 22

너희가 프로그래밍 갤러리인지 코딩 갤러리인지 테스트 하기 위한 문제이다. 코딩은 집어 치우고 어떻게 해결할 것인지 알고리즘만 말해라.