线段距离（dist）

本题使用文件输入输出，请在程序开头加入：

freopen("dist.in", "r", stdin);
freopen("dist.out", "w", stdout);

题目描述

Y 同学在数轴 $Ox$ 上拥有 $N$ 条带颜色的线段。每条线段可以用一个三元组 $(l_i, r_i, c_i)$ 来描述，其中 $[l_i, r_i]$ 表示该线段在数轴上覆盖的闭区间，$c_i$ 表示该线段的颜色，满足 $1 \le l_i \le r_i \le 10^9$ 且 $1 \le c_i \le N$。

Y 同学对线段之间的距离十分感兴趣。对于两条线段 $i$ 和 $j$，它们之间的距离 $d(i, j)$ 定义为：

$$d(i, j) = \min_{x \in [l_i, r_i], y \in [l_j, r_j]} \vert x - y \vert$$

显然，若两线段存在交点（包括端点重合），则它们之间的距离为 $0$。

Y 同学认为寻找同种颜色的线段之间的距离没有意义。因此，对于每一条线段 $i$，他希望求出该线段与所有与其颜色不同的线段之间的最小距离 $D_i$。即：

$$D_i = \min_{j: c_j \neq c_i} d(i, j)$$

保证输入中至少存在两条颜色不同的线段。

输入格式

从 dist.in 文件读入数据。

第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据： 第一行包含一个整数 $N$，表示线段的数量。 接下来的 $N$ 行，每行包含三个整数 $l_i, r_i, c_i$，分别表示第 $i$ 条线段的左端点、右端点和颜色。

输出格式

输出到 dist.out 文件。

对于每组测试数据，输出一行 $N$ 个整数，第 $i$ 个整数表示第 $i$ 条线段到最近的异色线段的距离 $D_i$。

样例

样例输入 #1

9
3
1 2 1
3 4 1
5 6 2
2
100000000 200000000 1
900000000 1000000000 2
5
1 2 1
2 3 2
3 4 3
4 5 4
5 6 5
5
1 5 1
4 9 2
1 2 1
8 9 2
5 7 3
2
1 100 2
10 90 1
3
1 1 1
10 10 2
1000000000 1000000000 3
3
3 4 1
2 5 1
1 6 2
6
5 6 2
11 12 3
7 8 2
3 4 2
1 2 1
9 10 2
2
1 3 1
2 3 2

样例输出 #1

3 1 1 
700000000 700000000 
0 0 0 0 0 
0 0 2 1 0 
0 0 
9 9 999999990 
0 0 0 
3 1 3 1 1 1 
0 0 

数据范围与约定

对于 $100\%$ 的数据，满足 $1 \le T \le 10^4$，$2 \le N \le 2 \cdot 10^5$，$\sum N \le 2 \cdot 10^5$，$1 \le l_i \le r_i \le 10^9$，$1 \le c_i \le N$。

测试点编号	分值	$N \le$	$\sum N \le$	特殊性质
$1 \sim 2$	$10$	$100$	$500$	无
$3 \sim 6$	$20$	$2000$	$4000$
$7 \sim 10$		$2 \cdot 10^5$		特殊性质 A
$11 \sim 14$				特殊性质 B
$15 \sim 20$	$30$			无

• 特殊性质 A：保证所有线段的颜色两两不同，即对于任意 $i \neq j$，均有 $c_i \neq c_j$。
• 特殊性质 B：保证所有线段的端点坐标 $\vert l_i \vert, \vert r_i \vert \le 2000$。