You are given an array of size N. For each index i, find the sum of largest, second largest and third largest element in the range [0,i] in the array

Input:-

First line contains 't', denoting the number of test cases. Then '2*t' lines follow, each containing the following:

First line of each test case contains n denoting the number of elements in the array.
Then, 'n' lines each containing 'n' space-separated integers, denoting the elements of the array.

Output:-

Print the answer for each index in each line. If there is no second largest or third largest number in the array A upto that index, then print "-1", without the quotes.

Constraints
1<=t<=100
1<=n<=10^4
0<=ai <10^10

Problem Setter
Shikhar Kunal