CF1916C.Training Before the Olympiad

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?

玛莎和奥莉娅即将迎来一场重要的团队奥林匹克竞赛。为此，玛莎提议和奥莉娅玩一个热身游戏：

给定一个长度为 $n$ 的数组 $a$。玛莎先手，双方轮流进行操作。每次操作按如下步骤进行：

$\bullet$ 若当前数组长度为 $1$，则游戏结束。

$\bullet$ 当前轮到行动的玩家选择两个不同的下标 $i$, $j$（满足 $1 \le i, j \le |a|$），执行如下操作：从数组中移除 $a_i$ 和 $a_j$，并向数组中加入一个新数 $\lfloor \frac{a_i + a_j}{2} \rfloor \cdot 2$。换言之，先将 $a_i$ 与 $a_j$ 的和除以 $2$ 并向下取整，再将结果乘以 $2$。

玛莎的目标是使最终剩余的数尽可能大，而奥莉娅的目标是使其尽可能小。

玛莎和奥莉娅决定在初始数组 $a$ 的每一个非空前缀上分别进行该游戏，并请求你的帮助。

对每个 $k = 1, 2, \ldots, n$，回答以下问题：仅保留数组 $a$ 的前 $k$ 个元素（对应下标为 $1, 2, \ldots, k$）参与游戏。在双方均采取最优策略的情况下，最终剩余的数是多少？

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$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）——数组的大小。

第二行包含 $n$ 个整数 $a_1,a_2, \ldots,a_n$（$1 \leq a_i \leq 10^9$）——玛莎和奥莉娅进行游戏的数组。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

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$.

对于每个测试用例，输出 $n$ 个整数。其中第 $k$ 个数应等于：在仅由数组 $a$ 的前 $k$ 个元素构成的数组上，双方均采取最优策略进行游戏后，最终剩余的数。

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$.

在第三个测试用例中，对于长度为 $1$ 的前缀，答案是 $3$；对于长度为 $2$ 的前缀，玛莎只有唯一一种操作方式，因此答案是 $12$；对于长度为 $3$ 的前缀，玛莎有三种可能的操作：选择 $3$ 和 $10$，最终得到的数为 $22$；选择 $3$ 和 $11$，最终得到的数为 $24$；选择 $10$ 和 $11$，最终得到的数为 $22$。因此玛莎将选择 $3$ 和 $11$，得到 $24$。