[Solution] Multi-Colored Segments Codeforces Solution

F. Multi-Colored Segments

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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≤𝑙𝑖≤𝑟𝑖≤109,1≤𝑐𝑖≤𝑛$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$0$.

For example, Dmitry has 5$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$0$.
• For the 3$3$-rd segment, the nearest segment of a different color is the 2$2$-nd segment, the distance to which is equal to 2$2$.
• For the 4$4$-th segment, the nearest segment of a different color is the 5$5$-th segment, the distance to which is equal to 1$1$.
• The 5$5$-th segment lies inside the 2$2$-nd segment (and these are segments of different colors), so the answers for them are equal to 0$0$.

Input

The first line of the input contains an integer 𝑡$t$ (1≤𝑡≤104$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≤𝑛≤2⋅105$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≤𝑙𝑖≤𝑟𝑖≤109,1≤𝑐𝑖≤𝑛$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$2$ segments of different colors.

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

Output

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.