该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

整数商店出售 $n$ 个区间。第 $i$ 个区间包含 $l_i$ 到 $r_i$ 之间的所有整数，价格为 $c_i$。

明天 Vasya 会去这家商店购买若干区间。他将获得所有被购买的区间内至少出现一次的整数。购买的总花费是所有购买区间价格之和。

购物后，Vasya 还能免费获得一些整数。整数 $x$ 能作为赠品获得，当且仅当同时满足：

• Vasya 没有购买 $x$；
• Vasya 购买了某个小于 $x$ 的整数 $l$；
• Vasya 购买了某个大于 $x$ 的整数 $r$。

每个整数最多只能被获得一次。

例如，如果 Vasya 购买了区间 $[2,4]$（花费 20）和 $[7,8]$（花费 22），他花费 42，直接获得 $2,3,4,7,8$，并免费获得 $5,6$。

由于技术原因，明天商店只有前 $s$ 个区间（即 $[l_1,r_1],[l_2,r_2],\dots,[l_s,r_s]$）可供购买。

Vasya 希望能获得尽可能多的整数。如果存在多种方式获得相同数量，他会选择花费最少的一种。

对于每个 $s=1..n$，求 Vasya 所需的最小花费。

输入格式

第一行一个整数 $t$，表示测试用例组数。($1\le t\le 1000$)

每组测试数据：

第一行一个整数 $n$ ($1\le n\le 10^5$)

接下来 $n$ 行，每行三个整数 $l_i,r_i,c_i$ ($1\le l_i\le r_i\le 10^9$, $1\le c_i\le 10^9$)

保证所有测试用例的 $n$ 之和不超过 $2\times 10^5$。

输出格式

对每组测试数据，输出 $n$ 个整数：第 $s$ 个整数表示仅前 $s$ 个区间可用时的最小花费。

输入输出样例

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

20
42
42
42
4
13
11
256
271
271