CF1741F.Multi-Colored Segments

Dmitry has $n$ segments of different colors on the coordinate axis $Ox$. Each segment is characterized by three integers $l_i$, $r_i$ and $c_i$ ($1 \le l_i \le r_i \le 10^9, 1 \le c_i \le n$), where $l_i$ and $r_i$ are are the coordinates of the ends of the $i$-th segment, and $c_i$ is its color.

Dmitry likes to find the minimum distances between segments. However, he considers pairs of segments of the same color uninteresting. Therefore, he wants to know for each segment the distance from this segment to the nearest differently colored segment.

The distance between two segments is the minimum of the distances between a point of the first segment and a point of the second segment. In particular, if the segments intersect, then the distance between them is equal to $0$.

For example, Dmitry has $5$ segments:

• The first segment intersects with the second (and these are segments of different colors), so the answers for them are equal to $0$.
• For the $3$-rd segment, the nearest segment of a different color is the $2$-nd segment, the distance to which is equal to $2$.
• For the $4$-th segment, the nearest segment of a different color is the $5$-th segment, the distance to which is equal to $1$.
• The $5$-th segment lies inside the $2$-nd segment (and these are segments of different colors), so the answers for them are equal to $0$.

德米特里在坐标轴 $Ox$ 上有 $n$ 条不同颜色的线段。每条线段由三个整数 $l_i$、$r_i$ 和 $c_i$（$1 \le l_i \le r_i \le 10^9$，$1 \le c_i \le n$）表征，其中 $l_i$ 和 $r_i$ 是第 $i$ 条线段两个端点的坐标，$c_i$ 是其颜色。

德米特里喜欢计算线段之间的最小距离。但他认为同色线段对是无趣的。因此，他希望对每条线段，求出它到最近的异色线段的距离。

两条线段之间的距离定义为：第一条线段上某点与第二条线段上某点之间距离的最小值。特别地，若两条线段相交，则它们之间的距离为 $0$。

例如，德米特里有 $5$ 条线段：

• 第一条线段与第二条线段相交（且二者颜色不同），因此它们的答案均为 $0$。
• 对于第三条线段，最近的异色线段是第二条线段，其距离为 $2$。
• 对于第四条线段，最近的异色线段是第五条线段，其距离为 $1$。
• 第五条线段完全位于第二条线段内部（且二者颜色不同），因此它们的答案均为 $0$。

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

The descriptions of the test cases follow.

The first line of description of each test case contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of segments.

The next $n$ lines contain descriptions of the segments. Each segment is described by three integers $l_i$, $r_i$ and $c_i$ ($1 \le l_i \le r_i \le 10^9, 1 \le c_i \le n$) — coordinates of the left and right ends of $i$-th segment, as well as the color of this segment. It is guaranteed that there are at least $2$ segments of different colors.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试数据中测试用例的数量。

随后是各测试用例的描述。

每个测试用例的描述以一行开始，该行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）——线段的数量。

接下来的 $n$ 行描述了这些线段。每条线段由三个整数 $l_i$、$r_i$ 和 $c_i$（$1 \le l_i \le r_i \le 10^9$，$1 \le c_i \le n$）描述——分别表示第 $i$ 条线段左端点和右端点的坐标，以及该线段的颜色。保证至少存在两条颜色不同的线段。

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

For each test case, on a separate line print $n$ integers, where the $i$-th number is equal to the distance from the $i$-th segment to the nearest segment of a different color.

对于每个测试用例，在单独的一行中输出 $n$ 个整数，其中第 $i$ 个数等于第 $i$ 个线段到颜色不同的最近线段的距离。

In the first test case of the first sample there is only one segment of color $2$, and all other segments have color $1$. Therefore, for segments of color $1$, the answer is equal to the distance to the $3$rd segment, and for $3$rd one, the answer is equal to the minimum of the distances to segments of color $1$.

In the second test case of the first sample there are only $2$ segments, and for both of them the answer is equal to the distance between them.

In the third test case of the first sample, each segment intersects at least one of its ends with a segment of a different color, so all answers are equal to $0$.

The fourth test case of the first sample is described in the problem statement.

In the fifth test case of the first sample, one segment lies completely inside the other, and for both of them the answer is $0$.

In the sixth test case of the first sample, all segments are points of different colors.

在第一个样例的第一组测试数据中，只有一段颜色为 $2$ 的线段，其余所有线段的颜色均为 $1$。因此，对于颜色为 $1$ 的线段，其答案等于到第 $3$ 段线段的距离；而对于第 $3$ 段线段，其答案等于到所有颜色为 $1$ 的线段的距离的最小值。

在第一个样例的第二组测试数据中，仅有 $2$ 段线段，且这两段线段的答案均等于它们之间的距离。

在第一个样例的第三组测试数据中，每一段线段至少有一个端点与某段不同颜色的线段相交，因此所有答案均为 $0$。

第一个样例的第四组测试数据已在题目描述中给出。

在第一个样例的第五组测试数据中，一段线段完全包含于另一段线段内部，且这两段线段的答案均为 $0$。

在第一个样例的第六组测试数据中，所有线段均为不同颜色的点。