玛莎和奥莉亚即将迎来一场重要的团体奥运会。为了纪念这一点,玛莎建议和奥莉亚玩一个游戏作为热身:
存在一个大小为 $$$n$$$ 的数组 $$$a$$$。玛莎先走,玩家轮流走。每个动作都由以下动作序列描述:
$$$\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$$$ 应该等于在由数组 $$$a$$$ 的第一个 $$$k$$$ 元素组成的数组上,最终双方玩家最佳发挥时保留的数字。
示例
输入 #1
4 1 31 6 6 3 7 2 5 4 3 3 10 11 5 7 13 11 19 1
输出 #1
31 6 8 16 18 22 26 3 12 24 7 20 30 48 50
注意
在第三个测试用例中,对于长度为 $$$1$$$ 的前缀,答案是 $$$3$$$。对于长度 $$$2$$$ 的前缀,玛莎只有一步,所以答案是 $$$12$$$。对于长度为 $$$3$$$ 的前缀,Masha 有三种可能的移动:她选择 $$$3$$$ 和 $$$10$$$,那么最终数字是 $$$22$$$、$$$3$$$ 和 $$$11$$$,那么最终数字是 $$$24$$$、$$$10$$$ 和 $$$11$$$,那么最终数字是 $$$22$$$,所以玛莎会选择 $$$3$$$ 和 $$$11$$$ 并得到 $$$24$$$。