E. Partitioning
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Note: You may want to use $$$64$$$-bit integers instead of $$$32$$$-bit integers in this task. For example, in Java, you may want to use long instead of int. In C++, you may want to use long long.

Sushang has a multiset $$$S$$$ containing $$$n$$$ elements and $$$k$$$ empty arrays $$$a_1,a_2,\ldots,a_k$$$. She will repeat the following operation until $$$S$$$ is empty:

  • Choose an element $$$x$$$ in $$$S$$$ and an integer $$$1\leq i\leq k$$$
  • Remove $$$x$$$ from $$$S$$$ and insert $$$x$$$ at the back of $$$a_i$$$

After that, Sushang calculates the score of each array as follows: if $$$a_i=[x_1,x_2,\ldots,x_m]$$$, then score$$$(a_i)=\sum_{i=1}^mx_i\cdot i=x_1\cdot1+x_2\cdot2+x_3\cdot3+\ldots+x_m\cdot m$$$. The score of an empty array is $$$0$$$.

Sushang wants to minimize the sum of scores over all arrays.

The value of $$$k$$$ is not yet known, so please find the minimum sum of scores possible for $$$k=1,2,\ldots,n$$$ independently.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) – the number of independent test cases. The description of test cases follow.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$) – the number of elements in $$$S$$$.

The second line of each test case contains $$$n$$$ integers $$$S_1,S_2,\ldots,S_n$$$ ($$$1 \leq S_i \leq 10^6$$$) – the numbers in the set $$$S$$$ initially.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Scoring

Partial credits will be given to programs who pass tests with smaller constraints outlined below.

GroupPointsConstraints
150The sum of $$$n$$$ does not exceed $$$3000$$$ over all test cases
250No further constraints
Output

For each test case, output $$$n$$$ numbers on a new line: the answer for $$$k=1,2,\ldots,n$$$.

Example
Input
4
3
1 1 1
3
1 2 3
1
1
8
3 1 4 1 5 9 2 6
Output
6 4 3
10 7 6
1
94 56 44 38 35 33 32 31
Note

In the first test case, when $$$k=3$$$, it is optimal to partition into the arrays $$$[1],[1],[1]$$$. Each array has a score of $$$1$$$.

In the second test case, when $$$k=2$$$, it is optimal to partition into the arrays $$$[3,1]$$$ and $$$[2]$$$. The first array has score $$$3\cdot1+1\cdot2=5$$$ and the second array has score $$$2$$$. The total score is $$$7$$$.