Fence

Bajtazar is widely believed to be the greatest scrooge in the borough. One can find many examples to support this claim, and the least important one is that his estate has no fence at all. However, he recently found $n$ old planks in his basement, so he decided to build at least a fragment of a fence.

He stacked the planks one over another so that their lengths, from the top, are $a_1, \ldots, a_n$. He took the first plank, cut off a piece of length $b$, and nailed it as the leftmost piece of the fence. He then cut another piece of length $b$ and nailed it next to the previous one. He kept doing this until what was left in his hand was a piece of length $c$ ($1 \leq c \leq b$). He nailed that short piece to the fence too, since it would be a pity to waste such a good plank. Then he took the second plank from the stack and repeated the whole procedure, and so on for every plank.

When the job was done, he decided the short pieces were a poor idea. He painted the whole fence white, but then he noticed that painting every other plank, starting from the leftmost one, uses about half as much paint and still looks coherent. So he painted only every second plank, starting from the leftmost one. (He could have started from the second one, after all.)

That night he wondered whether a different height $b$ would have needed less paint. For every possible height $b = 1, \ldots, M$, where $M$ is the largest $a_i$, compute the total length of planks he would have painted white.

The first line contains the number of test cases $z$ ($1 \leq z \leq 5$).

The first line of each test case contains the number of planks $n$ ($1 \leq n \leq 1\,000\,000$). The next $n$ integers are the plank lengths $a_1, \ldots, a_n$ ($1 \leq a_i \leq 1\,000\,000$, $\sum_{i=1}^n a_i \leq 1\,000\,000$).

For each test case, output $M$ lines, where $M$ is the largest $a_i$ in that test case. On line $i$, output $f_i$, the total length of planks Bajtazar would have painted white if he had chosen the fence height $b = i$.

For height $b = 4$, the fence pieces are 4 4 2 4 3 2 4 4. He would paint pieces with total length $4 + 2 + 3 + 4 = 13$, so the answer on line 4 is 13.

For height $b = 5$, the fence pieces are 5 5 5 2 2 5 3. He would paint pieces with total length $5 + 5 + 2 + 3 = 15$, so the answer on line 5 is 15.