C. 赛前训练

时间限制：每个测试 $1$ 秒
内存限制：每个测试 $256$ 兆字节

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

给定一个大小为 $n$ 的数组 $a$。玛莎先手，两人轮流进行。每一步的操作流程如下：

• 若数组的大小为 $1$，游戏结束。
• 当前操作的玩家选择两个不同的下标 $i$ 和 $j$（$1 \le i, j \le |a|$），执行以下操作——从数组中删除 $a_i$ 和 $a_j$，并向数组中添加一个数值等于 $\left\lfloor \frac{a_i + a_j}{2} \right\rfloor \cdot 2$ 的新元素。换句话说，先将 $a_i$ 与 $a_j$ 的和除以 $2$ 并向下取整，然后将结果乘以 $2$。

玛莎的目标是最大化最终剩下的数，而奥莉娅的目标则是将其最小化。

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

对于每个 $k = 1, 2, \dots, n$，回答如下问题：仅使用数组 $a$ 的前 $k$ 个元素（下标分别为 $1, 2, \dots, k$）进行游戏，在双方均采取最优策略的情况下，最后会剩下哪一个数？

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

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

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 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 

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