310976: CF1916C. Training Before the Olympiad

C. Training Before the Olympiadtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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

ExampleInput

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

Output

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

题目大意：
玛莎和奥尔加即将参加一场重要的团队奥林匹克比赛。为了热身，玛莎提议和奥尔加玩一个游戏。游戏规则如下：

- 有一个长度为n的数组a。
- 玛莎先手，轮流进行。
- 每轮操作如下：
- 如果数组长度为1，游戏结束。
- 当前玩家选择两个不同的下标i和j（1≤i,j≤|a|），然后执行以下操作：从数组中移除a_i和a_j，并向数组中添加一个数，该数为 ⌊(a_i + a_j)/2⌋ * 2。换句话说，就是先将a_i和a_j的和除以2并向下取整，然后将结果乘以2。
- 玛莎的目标是最大化最终的结果，而奥尔加的目标是最小化结果。

玛莎和奥尔加决定在数组a的每个非空前缀上进行游戏，并请求你的帮助。

对于每个k=1,2,…,n，回答以下问题：仅考虑数组a的前k个元素，下标分别为1,2,…,k。在双方都进行最优游戏的情况下，最终会剩下什么数？

输入数据格式：
- 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
- 每个测试用例的第一行包含一个整数n（1≤n≤10^5）——数组的大小。
- 第二行包含n个整数a_1,a_2,…,a_n（1≤a_i≤10^9）——玛莎和奥尔加游戏的数组。
- 保证所有测试用例的n之和不超过10^5。

输出数据格式：
- 对于每个测试用例，输出n个整数。第k个数表示仅考虑数组a的前k个元素时，在双方都进行最优游戏的情况下，最终会剩下的数。

示例：
输入：
```
4
1
31
6
6 3 7 2 5 4
3
3 10 11
5
7 13 11 19 1
```
输出：
```
31
6 8 16 18 22 26
3 12 24
7 20 30 48 50
```题目大意： 玛莎和奥尔加即将参加一场重要的团队奥林匹克比赛。为了热身，玛莎提议和奥尔加玩一个游戏。游戏规则如下： - 有一个长度为n的数组a。 - 玛莎先手，轮流进行。 - 每轮操作如下： - 如果数组长度为1，游戏结束。 - 当前玩家选择两个不同的下标i和j（1≤i,j≤|a|），然后执行以下操作：从数组中移除a_i和a_j，并向数组中添加一个数，该数为 ⌊(a_i + a_j)/2⌋ * 2。换句话说，就是先将a_i和a_j的和除以2并向下取整，然后将结果乘以2。 - 玛莎的目标是最大化最终的结果，而奥尔加的目标是最小化结果。 玛莎和奥尔加决定在数组a的每个非空前缀上进行游戏，并请求你的帮助。 对于每个k=1,2,…,n，回答以下问题：仅考虑数组a的前k个元素，下标分别为1,2,…,k。在双方都进行最优游戏的情况下，最终会剩下什么数？ 输入数据格式： - 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 - 每个测试用例的第一行包含一个整数n（1≤n≤10^5）——数组的大小。 - 第二行包含n个整数a_1,a_2,…,a_n（1≤a_i≤10^9）——玛莎和奥尔加游戏的数组。 - 保证所有测试用例的n之和不超过10^5。 输出数据格式： - 对于每个测试用例，输出n个整数。第k个数表示仅考虑数组a的前k个元素时，在双方都进行最优游戏的情况下，最终会剩下的数。 示例： 输入： ``` 4 1 31 6 6 3 7 2 5 4 3 3 10 11 5 7 13 11 19 1 ``` 输出： ``` 31 6 8 16 18 22 26 3 12 24 7 20 30 48 50 ```