CF1621B.Integers Shop

The integers shop sells $n$ segments. The $i$-th of them contains all integers from $l_i$ to $r_i$ and costs $c_i$ coins.

Tomorrow Vasya will go to this shop and will buy some segments there. He will get all integers that appear in at least one of bought segments. The total cost of the purchase is the sum of costs of all segments in it.

After shopping, Vasya will get some more integers as a gift. He will get integer $x$ as a gift if and only if all of the following conditions are satisfied:

• Vasya hasn't bought $x$.
• Vasya has bought integer $l$ that is less than $x$.
• Vasya has bought integer $r$ that is greater than $x$.

Vasya can get integer $x$ as a gift only once so he won't have the same integers after receiving a gift.

For example, if Vasya buys segment $[2, 4]$ for $20$ coins and segment $[7, 8]$ for $22$ coins, he spends $42$ coins and receives integers $2, 3, 4, 7, 8$ from these segments. He also gets integers $5$ and $6$ as a gift.

Due to the technical issues only the first $s$ segments (that is, segments $[l_1, r_1], [l_2, r_2], \ldots, [l_s, r_s]$) will be available tomorrow in the shop.

Vasya wants to get (to buy or to get as a gift) as many integers as possible. If he can do this in differents ways, he selects the cheapest of them.

For each $s$ from $1$ to $n$, find how many coins will Vasya spend if only the first $s$ segments will be available.

整数商店出售 $n$ 个区间。其中第 $i$ 个区间包含从 $l_i$ 到 $r_i$ 的所有整数，售价为 $c_i$ 枚金币。

明天，瓦夏将前往该商店购买若干区间。他将获得所有在至少一个所购区间中出现的整数。此次购物的总花费等于所购所有区间的费用之和。

购物结束后，瓦夏还将额外获得一些整数作为赠品。当且仅当满足以下全部条件时，整数 $x$ 将作为赠品赠送给他：

• 瓦夏未购买整数 $x$；
• 瓦夏购买了某个小于 $x$ 的整数 $l$；
• 瓦夏购买了某个大于 $x$ 的整数 $r$。

每个整数 $x$ 最多仅能作为赠品获得一次，因此瓦夏不会因获赠而得到重复的整数。

例如，若瓦夏以 $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]$）可供购买。

瓦夏希望尽可能多地获得整数（通过购买或获赠）。若存在多种方案可达成最大整数数量，则他选择其中总花费最小的方案。

对每个 $s$（从 $1$ 到 $n$），求出当仅有前 $s$ 个区间可用时，瓦夏需要花费多少枚金币。

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The first line of each test case contains the single integer $n$ ($1 \leq n \leq 10^5$) — the number of segments in the shop.

Each of next $n$ lines contains three integers $l_i$, $r_i$, $c_i$ ($1 \leq l_i \leq r_i \leq 10^9, 1 \leq c_i \leq 10^9$) — the ends of the $i$-th segments and its cost.

It is guaranteed that the total sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case output $n$ integers: the $s$-th ($1 \leq s \leq n$) of them should be the number of coins Vasia will spend in the shop if only the first $s$ segments will be available.

对于每个测试用例，输出 $n$ 个整数：其中第 $s$ 个整数（$1 \leq s \leq n$）表示当仅有前 $s$ 个线段可用时，Vasia 在商店中将花费的硬币数量。

In the first test case if $s = 1$ then Vasya can buy only the segment $[2, 4]$ for $20$ coins and get $3$ integers.

The way to get $7$ integers for $42$ coins in case $s = 2$ is described in the statement.

In the second test case note, that there can be the same segments in the shop.

在第一个测试用例中，若 $s = 1$，则 Vasya 只能以 $20$ 枚硬币购买区间 $[2, 4]$，从而获得 $3$ 个整数。

当 $s = 2$ 时，以 $42$ 枚硬币获得 $7$ 个整数的方法已在题目描述中给出。

在第二个测试用例中，请注意商店中可能出现相同的区间。