给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。
对于从 $$$1$$$ 到 $$$n$$$ 的每个整数 $$$k$$$,您必须执行以下操作:
- 选择$$$a$$$中的任意元素并将其移动到数组的右端(可以选择最后一个元素,则数组不会改变);
- 打印 $$$a$$$ 最后一个元素 $$$k$$$ 的总和;
- 将您在第一步中选择的元素移动到其原始位置(恢复原始数组 $$$a$$$)。
对于每个 $$$k$$$,您选择要移动的元素,以便打印的值是 最大可能.
计算每 $$$k$$$ 打印的值。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由两行组成:
- 第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$);
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。
对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印 $$$n$$$ 整数。如果 $$$k=i$$$,这些整数中的第 $$$i$$$ 应等于可以打印的最大值。
示例
输入复制
4713 5 10 14 8 15 1361000000000 1000000000 1000000000 1000000000 1000000000 100000000014227 5
输出复制
15 28 42 50 63 73 78 1000000000 2000000000 3000000000 4000000000 5000000000 6000000000 42 7 12
注意
让我们考虑语句中的第一个测试用例:
- 当$$$k = 1$$$时,可以将第$$$6$$$移动到最后,数组变为$$$[13, 5, 10, 14, 8, 13, 15]$$$,打印的值为$$$15$$$;
- 当$$$k = 2$$$时,可以将第$$$6$$$移动到最后,数组变为$$$[13, 5, 10, 14, 8, 13, 15]$$$,打印的值为$$$13 + 15 = 28$$$;
- 当$$$k = 3$$$时,可以将第$$$4$$$移动到最后,数组变为$$$[13, 5, 10, 8, 15, 13, 14]$$$,打印的值为$$$15 + 13 + 14 = 42$$$;
- 当$$$k = 4$$$时,可以将第$$$5$$$移动到最后,数组变为$$$[13, 5, 10, 14, 15, 13, 8]$$$,打印的值为$$$14 + 15 + 13 + 8 = 50$$$;
- 当$$$k = 5$$$时,可以将$$$1$$$-st元素移动到末尾,数组变为$$$[5, 10, 14, 8, 15, 13, 13]$$$,打印的值为$$$14 + 8 + 15 + 13 + 13 = 63$$$;
- 当$$$k = 6$$$时,可以将$$$1$$$-st元素移动到最后,数组变为$$$[5, 10, 14, 8, 15, 13, 13]$$$,打印的值为$$$10 + 14 + 8 + 15 + 13 + 13 = 73$$$;
- 当$$$k = 7$$$时,可以将第$$$6$$$移动到末尾,数组变为$$$[13, 5, 10, 14, 8, 13, 15]$$$,打印的值为$$$13 + 5 + 10 + 14 + 8 + 13 + 15 = 78$$$。