您有 $$$n$$$ 硬币,面额为 $$$a_1、a_2、\ldots、a_n$$$ 和自然数 $$$k$$$。您还有一个袋子,最初是空的,您可以在其中放置硬币。您需要准确执行 $$$k$$$ 操作。在每个动作中,您从剩下的硬币中取出一枚硬币并将其放入您的包中。之后,你就不能再拿走那枚硬币了。
同时,你有一只喜欢偶数的猫,所以每当你包里的硬币面额之和变成偶数时,你的猫就会清空包里的东西,这意味着它会把所有的硬币带到一个只有它知道的地方,然后包里又空了。请注意,在添加硬币的过程中,每次金额变为偶数时,袋子都会被清空,而不仅仅是在最后一刻。
让你的分数为袋子里硬币面值的总和。您的任务是执行 $$$k$$$ 操作,以使您的最终得分最大化。找出所有 $$$1 \le k \le n$$$ 的答案。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,输出 $$$n$$$ 数字 — 通过对从 $$$1$$$ 到 $$$n$$$ 的所有 $$$k$$$ 执行精确 $$$k$$$ 操作可以获得的最大可能分数。
示例
输入复制
631 1 131 2 354 1 3 1 254 2 3 1 334 1 234 2 2
输出复制
1 0 13 5 03 7 9 7 93 7 9 7 91 5 70 0 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$$$。