Turtle 刚刚收到 $$$n$$$ 段和序列 $$$a_1, a_2, \ldots, a_n$$$。第$$$i$$$段是$$$[l_i, r_i]$$$。
Turtle 将创建一个无向图 $$$G$$$。如果线段 $$$i$$$ 和线段 $$$j$$$ 相交,则 Turtle 将为每个 $$$i \ne j$$$ 在 $$$i$$$ 和 $$$j$$$ 之间添加一条权重为 $$$|a_i - a_j|$$$ 的无向边。
Turtle 希望您计算图 $$$G$$$ 的最小生成树的边的权重之和,或者报告图 $$$G$$$ 没有生成树。
我们说两条线段 $$$[l_1, r_1]$$$ 和 $$$[l_2, r_2]$$$ 相交当且仅当 $$$\max(l_1, l_2) \le \min(r_1, r_2)$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — 段数。
以下 $$$n$$$ 行中的第 $$$i$$$ 行包含三个整数 $$$l_i, r_i, a_i$$$ ($$$1 \le l_i \le r_i \le 10^9, 1 \le a_i \le 10^9$$$) — 第 $$$i$$$ 段和第 $$$i$$$序列的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 图 $$$G$$$ 的最小生成树的边的权重之和。如果图$$$G$$$没有生成树,则输出$$$-1$$$。
示例
输入 #1
4 5 1 7 3 2 4 6 3 5 5 6 7 9 3 4 4 5 2 7 3 1 3 6 4 5 5 6 7 9 1 1 4 4 1 4 3 1 2 1 3 4 5 1 4 4 3 1 3 1 2 3 3 4 5 8
输出 #1
9 13 4 -1
注意
第一个测试用例中,图形$$$G$$$如下:
$$$G$$$的最小生成树之一如下:
最小生成树边的权重之和为$$$9$$$。
在第二个测试用例中,图形$$$G$$$如下:
$$$G$$$ 已经是一棵树,树的权重总和是 $$$13$$$。
在第三个测试用例中,图形$$$G$$$如下:
在第四个测试用例中,图形$$$G$$$如下:
很容易看出$$$G$$$没有连通,因此$$$G$$$没有生成树。