#P1916C. Training Before the Olympiad

    ID: 10284 Type: RemoteJudge 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: 4 Uploaded By: Tags>constructive algorithmsgamesgreedyimplementationmath*1200

Training Before the Olympiad

Description

Masha and Olya have an important team olympiad coming up soon. In honor of this, Masha, for warm-up, suggested playing a game with Olya:

There is an array aa of size nn. Masha goes first, and the players take turns. Each move is described by the following sequence of actions:

\bullet If the size of the array is 11, the game ends.

\bullet The player who is currently playing chooses two different indices ii, jj (1i,ja1 \le i, j \le |a|), and performs the following operation — removes aia_i and aja_j from the array and adds to the array a number equal to ai+aj22\lfloor \frac{a_i + a_j}{2} \rfloor \cdot 2. In other words, first divides the sum of the numbers aia_i, aja_j by 22 rounding down, and then multiplies the result by 22.

Masha aims to maximize the final number, while Olya aims to minimize it.

Masha and Olya decided to play on each non-empty prefix of the initial array aa, and asked for your help.

For each k=1,2,,nk = 1, 2, \ldots, n, answer the following question. Let only the first kk elements of the array aa be present in the game, with indices 1,2,,k1, 2, \ldots, k respectively. What number will remain at the end with optimal play by both players?

The first line contains an integer tt (1t1041 \leq t \leq 10^4) — the number of test cases.

The first line of each test case contains a single integer nn (1n1051 \le n \le 10^5) — the size of the array.

The second line contains nn integers a1,a2,,ana_1,a_2, \ldots,a_n (1ai1091 \leq a_i \leq 10^9) — the array on which Masha and Olya play.

It is guaranteed that the sum of nn over all test cases does not exceed 10510^5.

For each test case, output nn integers. The kk-th of these numbers should be equal to the number that will remain at the end with optimal play by both players, on the array consisting of the first kk elements of the array aa.

Input

The first line contains an integer tt (1t1041 \leq t \leq 10^4) — the number of test cases.

The first line of each test case contains a single integer nn (1n1051 \le n \le 10^5) — the size of the array.

The second line contains nn integers a1,a2,,ana_1,a_2, \ldots,a_n (1ai1091 \leq a_i \leq 10^9) — the array on which Masha and Olya play.

It is guaranteed that the sum of nn over all test cases does not exceed 10510^5.

Output

For each test case, output nn integers. The kk-th of these numbers should be equal to the number that will remain at the end with optimal play by both players, on the array consisting of the first kk elements of the array aa.

Sample Input 1

4
1
31
6
6 3 7 2 5 4
3
3 10 11
5
7 13 11 19 1

Sample Output 1

31 
6 8 16 18 22 26 
3 12 24 
7 20 30 48 50

Note

In the third test case, for a prefix of length 11, the answer is 33. For a prefix of length 22, Masha has only one move, so the answer is 1212. For a prefix of length 33, Masha has three possible moves: she chooses 33 and 1010, then the final number is 2222, 33 and 1111, then the final number is 2424, 1010 and 1111, then the final number is 2222, so Masha will choose 33 and 1111 and get 2424.