Training Before the Olympiad
Contest: Good Bye 2023
Difficulty rating: 1200
Tags: constructive algorithms, games, greedy, implementation, math

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 $$$a$$$ of size $$$n$$$. 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 $$$1$$$, the game ends.

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

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 $$$a$$$, and asked for your help.

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

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

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

The second line contains $$$n$$$ integers $$$a_1,a_2, \ldots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the array on which Masha and Olya play.

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

Output format:
For each test case, output $$$n$$$ integers. The $$$k$$$-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 $$$k$$$ elements of the array $$$a$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the third test case, for a prefix of length $$$1$$$, the answer is $$$3$$$. For a prefix of length $$$2$$$, Masha has only one move, so the answer is $$$12$$$. For a prefix of length $$$3$$$, Masha has three possible moves: she chooses $$$3$$$ and $$$10$$$, then the final number is $$$22$$$, $$$3$$$ and $$$11$$$, then the final number is $$$24$$$, $$$10$$$ and $$$11$$$, then the final number is $$$22$$$, so Masha will choose $$$3$$$ and $$$11$$$ and get $$$24$$$.

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

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

Editorial:
Note that our operation replaces two numbers with their sum if they are of the same parity, and with their sum $$$-1$$$ otherwise. Therefore, the second player needs to perform as many operations as possible where an even and an odd number are used. Also, note that on any move of the second player, there will be at least one even number that the first player made on the previous move. Then our task for the first player is to remove two odd numbers as often as possible. It can also be observed that the number of odd numbers in the array does not decrease, which means all operations with two odd numbers will go before operations with two even numbers. And after each such move, the second player will remove one odd number from the array. That is, in two moves, the number of odd numbers decreases by $$$3$$$. Let's consider all possible remainders of the number of odd numbers modulo $$$3$$$. If the remainder is $$$0$$$, then the answer is $$$sum - \frac{cnt}{3}$$$, where $$$sum$$$ is the sum of all numbers. If the remainder modulo is $$$1$$$, then two situations are possible: when the size of the array is $$$1$$$ — then the answer is the single number in the array. Otherwise, at the moment when there is $$$1$$$ odd number left, there will be one more move of player number $$$2$$$, which means he will reduce the total sum once more, and the answer will be $$$sum - \lfloor \frac{cnt}{3} \rfloor - 1$$$. If the remainder modulo is $$$2$$$, then the number of moves when the second player reduces the sum does not change, so the answer is $$$sum - \lfloor \frac{cnt}{3} \rfloor$$$.