CF2176C Odd Process

你有 $n$ 枚硬币，面额分别为 $a_1, a_2, \ldots, a_n$，还有一个自然数 $k$。你有一个最开始为空的包，你可以把硬币放进去。你需要恰好进行 $k$ 次操作，每次操作选一个剩下的硬币放进包里，该硬币之后不能再选。 同时，你有一只非常喜欢偶数的猫，每当你包内硬币的面额和变为偶数时，猫就会把包清空，也就是它把包里所有硬币都带走了，包会变为空。注意，只要放了一个硬币后包内的和变为偶数，无论在什么时候，猫都会立刻把包清空，不仅仅是在最后一步。 记你的得分为包中硬币面额的和。你的任务是，用 $k$ 次操作让最终分数最大。请你计算所有 $1 \leq k \leq n$ 时的最大可能最终分数，并输出。

每个测试包含多组数据。第一行为测试组数 $t$（$1 \leq t \leq 10^4$）。 每组数据的第一行包含一个正整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示硬币数量。 每组数据的第二行包含 $n$ 个自然数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示硬币的面额。 保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组数据，输出 $n$ 个数，第 $k$ 个数表示恰好进行 $k$ 次操作后的最大可能得分。每组输出占一行。

在第一组输入数据中，你有面额为 $1,1,1$ 的硬币。 - $k=1$：不论选哪枚硬币，包里和都是 $1$，最终得分也是 $1$。 - $k=2$：无论选择哪两枚硬币，初始面额和为 $1$，第二次操作后和为 $2$，此时包被清空，最终得分为 $0$。 - $k=3$：前两步包中和为 $2$，包被清空，包变空。第三步再选一枚硬币，和为 $1$。 在第二组输入数据中，你有面额为 $1,2,3$ 的硬币。 - $k=1$：选面额为 $2$ 的硬币时，包被猫清空，最终得分为 $0$。选 $1$ 或 $3$，得分分别为 $1$ 和 $3$。最大分为 $3$。 - $k=2$：选择 $1$ 和 $3$ 时，和为 $4$，包被猫清空。若第一步选 $3$，得分为 $3$，第二步选 $2$，总分为 $5$。 - $k=3$：所有硬币都选上，总和为 $6$，但每到偶数时包会被清空，最终分数为 $0$。 由 ChatGPT 5 翻译