CF1916C Training Before the Olympiad

Masha 和 Olya 即将参加一场重要的团队奥林匹克竞赛。为此，Masha 提议和 Olya 玩一个热身游戏： 有一个长度为 $n$ 的数组 $a$。Masha 先手，双方轮流操作。每一步操作如下： $\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$。 Masha 的目标是让最终剩下的数最大，Olya 的目标是让最终剩下的数最小。 Masha 和 Olya 决定对初始数组 $a$ 的每一个非空前缀都玩一遍这个游戏，并向你寻求帮助。 对于每个 $k = 1, 2, \ldots, n$，请回答如下问题：仅用数组 $a$ 的前 $k$ 个元素（下标为 $1, 2, \ldots, k$）进行游戏，双方都采取最优策略，最后剩下的数是多少？

第一行包含一个整数 $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$）——Masha 和 Olya 玩游戏用的数组。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出 $n$ 个整数。第 $k$ 个数表示在仅用数组前 $k$ 个元素进行游戏、双方都采取最优策略时，最后剩下的数是多少。

在第三个测试用例中，对于长度为 $1$ 的前缀，答案是 $3$。对于长度为 $2$ 的前缀，Masha 只有一种操作方式，答案是 $12$。对于长度为 $3$ 的前缀，Masha 有三种选择：选择 $3$ 和 $10$，最终剩下 $22$；选择 $3$ 和 $11$，最终剩下 $24$；选择 $10$ 和 $11$，最终剩下 $22$，因此 Masha 会选择 $3$ 和 $11$，最终得到 $24$。 由 ChatGPT 4.1 翻译