整数商店出售 $$$n$$$ 段。其中第 $$$i$$$ 包含从 $$$l_i$$$ 到 $$$r_i$$$ 的所有整数,并花费 $$$c_i$$$ 硬币。
明天 Vasya 会去这家商店并在那里购买一些片段。他将获得至少出现在购买的一个段中的所有整数。采购总成本是采购中所有环节成本的总和。
购物后,Vasya将获得更多整数作为礼物。当且仅当满足以下所有条件时,他才会获得整数 $$$x$$$ 作为礼物:
- Vasya 尚未购买 $$$x$$$。
- Vasya 购买了小于 $$$x$$$ 的整数 $$$l$$$。
- Vasya 购买了大于 $$$x$$$ 的整数 $$$r$$$。
Vasya 只能获得一次整数 $$$x$$$ 作为礼物,因此他在收到礼物后不会拥有相同的整数。
例如,如果 Vasya 以 $$$20$$$ 硬币购买段 $$$[2, 4]$$$,并以 $$$22$$$ 硬币购买段 $$$[7, 8]$$$,则他花费 $$$42$$$ 硬币并从这些段接收整数 $$$2, 3, 4, 7, 8$$$。他还得到整数 $$$5$$$ 和 $$$6$$$ 作为礼物。
由于技术问题,明天商店中仅提供前 $$$s$$$ 段(即段 $$$[l_1, r_1], [l_2, r_2], \ldots, [l_s, r_s]$$$)。
Vasya 想要获得(购买或作为礼物获得)尽可能多的整数。如果他可以通过不同的方式做到这一点,他会选择其中最便宜的。
对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$s$$$,找出如果只有前 $$$s$$$ 段可用,Vasya 将花费多少硬币。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。
每个测试用例的第一行包含单个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 商店中的段数。
接下来的 $$$n$$$ 行包含三个整数 $$$l_i$$$、$$$r_i$$$、$$$c_i$$$ ($$$1 \leq l_i \leq r_i \leq 10^9, 1 \leq c_i \leq 10^9$$$) — 第 $$$i$$$ 段的末尾及其成本。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例输出 $$$n$$$ 整数:其中的第 $$$s$$$ ($$$1 \leq s \leq n$$$) 应该是 Vasia 在商店中花费的硬币数量(如果只有前 $$$s$$$ 段可用)。
示例
输入 #1
3 2 2 4 20 7 8 22 2 5 11 42 5 11 42 6 1 4 4 5 8 9 7 8 7 2 10 252 1 11 271 1 10 1
输出 #1
20 42 42 42 4 13 11 256 271 271
注意
在第一个测试用例中,如果 $$$s = 1$$$,则 Vasya 只能用 $$$20$$$ 硬币购买 $$$[2, 4]$$$ 段并获得 $$$3$$$ 整数。
语句中描述了在 $$$s = 2$$$ 的情况下获得 $$$42$$$ 硬币的 $$$7$$$ 整数的方法。
在第二个测试用例中请注意,商店中可以存在相同的段。