apple-picking

After Apple Picking is a famous poem by Robert Frost. It describes what all joys come to the farmer  (the apple picker) before the harvest and what all pains he has to go through after wards. Chandan, our farmer, is very fond of poetry. He has read the poem too, and is afraid of the after effects he might have to face.

There are 3 days left before the apple sale in the market, and Chandan has to finish his work of apple picking in these three days. There are N trees in his farm, and he knows how many apples are there on each of the tree. Everyday he has to choose a certain set of trees and pluck all apples from them. His work of plucking apples from all the trees has to complete somehow in these three days otherwise he will go on a loss . Afraid of being too tired, Chandan wants to collect as equal number of apples each day as possible. Also he is a slow starter, so out of the three days, he will collect least on day1 and most on day3.

Input & Output

The first line of the the input file will contains the number of test cases T. Then follows the description of each test case. Each test case has 2 lines. The first contains the number of trees N. The next line has N space separated integers which are the number of apples in each tree.

For each test case, output a line which is the required answer of work equalization. This line should contains 3 space numbers, the number of apples plucked on each of the three days.

Constraints:

T ≤ 2^3
2^0 ≤ N ≤ 2^4 + 2^2
2^0 ≤ apples in any tree ≤ 2^30

SAMPLE INPUT
2
3
2 3 1
2
1 2

SAMPLE OUTPUT
1 2 3
0 1 2

Explanation

1) In the first sample, he has no other choice than to collect 1, 2 and 3 apples respectively on each of the days. 

2) In the second sample, note that you have to output 0 if he isnt collecting anything on a particular day.

Source: hackerearth | Difficulty: HARD
Tags: Geometry


Solutions: