Find out the maximum sub-array of non negative numbers from an array. 

The sub-array should be continuous. That is, a sub-array created by choosing the second and fourth element and skipping the third element is invalid.

Maximum sub-array is defined in terms of the sum of the elements in the sub-array. Sub-array A is greater than sub-array B if sum(A) > sum(B).

NOTE 1 :If there is a tie, then compare with segment's length and return segment which has maximum length 

NOTE 2: If there is still a tie, then return the segment with minimum starting index.

-----Input-----

The first line contains the number of test cases. Each test cases contains an integer N. next line consists of N integers, the elements of the array.

-----Output-----

Print out the maximum sub-array as stated above.

-----Constraints-----
-  1  ≤  T  ≤  100 
-  1  ≤  N  ≤  105 
-  1  ≤  Ai  ≤  105 

-----Example-----
Input:

1
6
1 2 5 -7 2 3

Output:

1 2 5

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	l = []
	for i in range(n):
		if a[i] < 0:
			e = i
			ss = sum(a[s:e])
			l.append((ss, e - s, n - s))
			s = i + 1
	e = n
	ss = sum(a[s:e])
	l.append((ss, e - s, n - s))
	x = max(l)
	s = n - x[2]
	e = x[1] + s
	for i in range(s, e):
		print(a[i], end=' ')
	print('')