CF2176C.Odd Process

You have $n$ coins with denominations $a_1, a_2, \ldots, a_n$ and a natural number $k$. You also have a bag, which is initially empty, where you can place coins. You need to perform exactly $k$ actions. In each action, you take one coin from those you have left and put it in your bag. After that, you can no longer take that coin.

At the same time, you have a cat that loves even numbers, so every time the sum of the denominations of the coins in your bag becomes even, your cat empties the bag, meaning it takes all the coins to a place known only to it, and the bag is empty again. Note that the bag is emptied every time the sum becomes even during the process of adding coins, not just at the very last moment.

Let your score be the sum of the denominations of the coins in the bag. Your task is to perform $k$ actions such that your final score is maximized. Find the answer for all $1 \le k \le n$.

你有 $n$ 枚硬币，面值分别为 $a_1, a_2, \ldots, a_n$，以及一个自然数 $k$。你还拥有一个初始为空的袋子，可用于放入硬币。你需要恰好执行 $k$ 次操作。每次操作中，你从剩余未使用的硬币中选取一枚放入袋中；此后该硬币便不可再使用。

与此同时，你有一只喜爱偶数的猫：每当袋中硬币面值之和变为偶数时，猫便会清空袋子——即把袋中所有硬币取走（去向只有它自己知道），袋子随即再次变为空。注意：袋子会在添加硬币过程中每次和变为偶数时立即被清空，而不仅限于最终时刻。

你的得分为袋中硬币面值之和。你的任务是执行 $k$ 次操作，使得最终得分最大化。对所有 $1 \le k \le n$，求出对应的最大得分。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of coins you have.

The second line of each test case contains $n$ natural numbers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the denominations of the coins.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 表示你拥有的硬币数量。

每个测试用例的第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）—— 表示硬币的面值。

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

For each test case, output $n$ numbers — the maximum possible score that can be achieved by performing exactly $k$ actions for all $k$ from $1$ to $n$.

对于每个测试用例，输出 $n$ 个数字——即对所有从 $1$ 到 $n$ 的 $k$，恰好执行 $k$ 次操作所能达到的最大可能得分。

In the first set of input data, you have coins with denominations [$1,1,1$].

• $k=1$: in this case, the sum of the denominations in the bag is $1$, regardless of the chosen coin. The final score is also $1$.
• $k=2$: in this case, the sum of the denominations in the bag is initially $1$, regardless of the choice of coin. When choosing the second coin, the sum will be $2$, regardless of the choice of coin, and thus the bag will be emptied. The final score is $0$.
• $k=3$: in this case, when choosing the first two coins, the sum will be $2$ and the bag will be emptied, after which the sum will be $0$. When choosing the third coin, the sum will become $1$.

In the second set of input data, you have coins with denominations [$1,2,3$].

• $k=1$: in this case, when choosing the coin with denomination $2$, the bag will be emptied and the final score will be $0$. When choosing the coin with denomination $1$ or $3$, the final scores will be $1$ and $3$, respectively. The maximum possible final score is $3$.
• $k=2$: in this case, when choosing two coins $1$ and $3$ in any order, their sum will be $4$, after which the bag will be emptied and the final score will be $0$. However, when choosing $3$ as the first coin, the score will be $3$. Then you can choose, for example, coin $2$, and the final score will become $5$.
• $k=3$: in this case, the sum of all coins will be $6$, and since each time the bag is emptied it does not change the parity of the accumulated sum, the final score is $0$.

在第一组输入数据中，你拥有的硬币面值为 [$1,1,1$]。

• $k=1$：此时，无论选择哪枚硬币，袋中面值之和均为 $1$，最终得分为 $1$。
• $k=2$：此时，无论首先选择哪枚硬币，袋中初始面值之和均为 $1$；当选择第二枚硬币后，面值之和变为 $2$，袋子被清空，最终得分为 $0$。
• $k=3$：此时，当选择前两枚硬币时，面值之和达到 $2$，袋子被清空，此时和变为 $0$；再选择第三枚硬币后，面值之和变为 $1$。

在第二组输入数据中，你拥有的硬币面值为 [$1,2,3$]。

• $k=1$：此时，若选择面值为 $2$ 的硬币，则袋子被清空，最终得分为 $0$；若选择面值为 $1$ 或 $3$ 的硬币，则最终得分分别为 $1$ 和 $3$。可能的最大最终得分为 $3$。
• $k=2$：此时，若以任意顺序选择面值为 $1$ 和 $3$ 的两枚硬币，其和为 $4$，袋子被清空，最终得分为 $0$；但若首先选择面值为 $3$ 的硬币，则当前得分为 $3$；随后可再选择（例如）面值为 $2$ 的硬币，最终得分变为 $5$。
• $k=3$：此时，所有硬币面值之和为 $6$；由于每次袋子被清空均不改变累计和的奇偶性，最终得分为 $0$。