题目描述

题目背景

永远亭的药房中，弥漫着千年不变的、让人安心的草药清香。因幡帝一边将晒干的蓬莱玉枝分门别类，一边嘴里碎碎念：“真是的，永琳师傅为什么总喜欢研究这些需要捣上千次的药嘛，铃仙那家伙又太老实，让她捣一万次都不会偷懒的……”

被念叨的铃仙·优昙华院·稻叶，此刻正跪坐在药臼前，长长的兔耳因专注而笔直竖起。她握着沉重的药杵，一下，又一下，遵循着最标准的节奏和力道捣着钵中的药材，发出沉闷而规律的“咚、咚”声。她的额角有细密的汗珠，眼神却无比认真，仿佛这不是捣药，而是一场严肃的仪式。

八意永琳不知何时悄然出现在门口，她看着铃仙的背影，眼中闪过一丝不易察觉的赞许。她走近，没有评价药的质量，只是伸出手，轻轻拂去铃仙发梢沾上的一点药草碎屑。

“今天的状态很不错，铃仙。”

就是这么一句简单的夸奖。

“是！永琳师……诶？！”铃仙下意识应答，然后才反应过来，那双总是透着些许不安的红色眼眸瞬间睁大。最明显的反应是她那对长长的耳朵——它们不受控制地、飞快地抖动了两下，然后“唰”地变得通红，连耳尖都仿佛在冒热气。她慌忙低下头，捣药的动作都乱了半拍。“非、非常感谢您的夸奖！”

帝在一旁看着，偷偷做了个鬼脸，但分类药材的动作，也不自觉地更轻快了些。窗外，那轮温柔的、人造的月亮，将清辉洒进永远亭，仿佛也在无声地微笑。

题目描述

给定一个长度为 \(n\) 的数列 \(a_1, a_2, \cdots, a_n\) 和一个定值 \(x\)。 铃仙和因幡帝依次选数，选完后立刻删除该数。

• 铃仙每次可以选任意一个数 \(a_i\)；
• 因幡帝每次必须选头部的前 \(x\) 个数，即 \(a_1, a_2, \cdots, a_x\)。若当前数列个数小于 \(x\) 个，则全部选完。

铃仙先选，随后轮流选数，直至数列为空。铃仙想要最大化铃仙所选之数的和，即假设铃仙选取了 \(a_{k_1}, a_{k_2}, \cdots, a_{k_m}\) （\(1 \le k_1 < k_2 < \cdots < k_m \le n\)），铃仙想要最大化 \(\sum_{i = 1}^m a_{k_i}\)。假设铃仙采用最优策略，对所有的 \(x = 1, 2, 3, \cdots, n-1\)，分别独立求出铃仙最大化的所选之数的和。

输入格式

输入的第一行包含一个整数 \(t\) （\(1 \le t \le 1000\)），表示测试用例的数量。

接下来是 \(t\) 个测试用例的描述。

每个测试用例的第一行包含一个整数 \(n\) （\(2 \le n \le 2 \times 10^5\)），表示给定数列的长度。

每个测试用例的第二行包含 \(n\) 个正整数 \(a_i\) （\(1 \le a_i \le 10^9\)），表示给定数列中的每一个数。

保证所有测试用例中 \(n\) 的总和不超过 \(5 \times 10^5\)。

输出格式

对于每个测试用例，输出一行，包含 \(n-1\) 个正整数，第 \(i\) 个整数表示当 \(x = i\) 时铃仙最大化的所选之数的和。

样例输入

3
2
1 2
6
1 1 4 5 1 4
11
12 11 10 9 1 2 3 4 5 12 11

样例输出

2
13 9 9 9 5
54 44 35 35 24 24 24 24 23 12

提示

在样例测试用例 2 中，初始时刻数列为 \(1, 1, 4, 5, 1, 4\)。

当 \(x = 1\) 时，一种铃仙最大化所选之数的和的方案为：

• 铃仙先选取 \(a_4 = 5\)，删除该数，此时数列为 \(1, 1, 4, 1, 4\)；
• 因幡帝必须选取头部的 \(1\) 个元素 \(a_1 = 1\)，此时数列为 \(1, 4, 1, 4\)；
• 铃仙再选取 \(a_2 = 4\)，此时数列为 \(1, 1, 4\)；
• 因幡帝必须选取头部的 \(1\) 个元素 \(a_1 = 1\)，此时数列为 \(1, 4\)；
• 铃仙再选取 \(a_2 = 4\)，此时数列为 \(1\)
• 因幡帝必须选取头部的 \(1\) 个元素 \(a_1 = 1\)，此时数列为空，停止。

铃仙所选之数的和为 \(5+4+4 = 13\)。可以证明的，该方案铃仙所选之数的和最大。

当 \(x = 3\) 时，一种铃仙最大化所选之数的和的方案为：

• 铃仙先选取 \(a_4 = 5\)，删除该数，此时数列为 \(1, 1, 4, 1, 4\)；
• 因幡帝必须选取头部的 \(3\) 个元素 \(a_1 = 1, a_2 = 1, a_3 = 4\)，此时数列为 \(1, 4\)；
• 铃仙再选取 \(a_2 = 4\)，此时数列为 \(1\)；
• 因幡帝必须选取头部的 \(3\) 个元素，但当且数列大小小于 \(3\)，全部取完，此时数列为空，停止。

铃仙所选之数的和为 \(5+4 = 9\)。可以证明的，该方案铃仙所选之数的和最大。