你是博物馆的保安。
博物馆的正门既是入口也是出口。每秒最多可以有一个人进门。有一个传感器可以检测访客何时通过门。传感器既无法确定参观者是谁,也无法确定他是否进入或离开了博物馆。传感器在 $$$2n$$$ 不同时刻 $$$a_1, a_2, \ldots, a_{2n}$$$(以秒为单位)检测到一些活动。
对于每个访客来说,他的停留时间等于退出时间减去进入时间。
现在博物馆已关闭(因此没有游客),您想知道今天可能的最大总停留时间,即今天进入博物馆的所有游客可能的最大停留时间之和。第二次$$$0$$$,博物馆也关门了。
出于安全考虑,博物馆内同时停留的人数也有限制,但你忘记了这个限制。对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$k$$$,您想要确定今天可能的最大总停留时间,假设最多 $$$k$$$ 人可以同时留在博物馆。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$),表明传感器在 $$$2n$$$ 不同时刻检测到某些活动。
每个测试用例的第二行包含 $$$2n$$$ 整数 $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$1 \leq a_1 \lt a_2 \lt \ldots \lt a_{2n} \leq 10^9$$$) - 传感器检测到某些活动的秒数。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印 $$$n$$$ 整数:对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$k$$$,打印今天可能的最大总停留时间,假设最多 $$$k$$$ 人可以同时留在博物馆。
示例
输入复制
3132 7824 5 6 946149048 26582657 36124499 43993239 813829899 860114890 910238130 913669539
输出复制
464 678018749 1737022233 1845329695 3385003015
注意
在第一个测试用例中,传感器在 $$$32$$$ 和 $$$78$$$ 秒处检测到活动。回想一下,$$$k$$$ 是可以同时留在博物馆的最大人数。
- 如果 $$$k$$$ 为 $$$1$$$,则最大可能总停留时间为 $$$46$$$,如果访客 $$$1$$$ 在时间 $$$32$$$ 进入并在时间 $$$78$$$ 退出,则达到该值。
在第二个测试用例中,传感器在 $$$4$$$、$$$5$$$、$$$6$$$ 和 $$$9$$$ 秒处检测到活动。
- 如果 $$$k$$$ 为 $$$1$$$,则最大可能总停留时间为 $$$4$$$,如果访问者 $$$1$$$ 在时间 $$$4$$$ 进入并在时间 $$$5$$$ 退出,并且访问者 $$$2$$$ 在时间 $$$6$$$ 进入并在时间 $$$9$$$ 退出,则达到最大总停留时间。
- 如果 $$$k$$$ 为 $$$2$$$,则最大可能总停留时间为 $$$6$$$,如果访问者 $$$1$$$ 在时间 $$$4$$$ 进入并在时间 $$$9$$$ 退出,并且访问者 $$$2$$$ 在时间 $$$5$$$ 进入并在时间 $$$6$$$ 退出,则达到最大总停留时间。