## Multi-Colored Segments solution codeforces

**Multi-Colored Segments solution codeforces** – Dmitry has 𝑛n segments of different colors on the coordinate axis 𝑂𝑥Ox. Each segment is characterized by three integers 𝑙𝑖li, 𝑟𝑖ri and 𝑐𝑖ci (1≤𝑙𝑖≤𝑟𝑖≤109,1≤𝑐𝑖≤𝑛1≤li≤ri≤109,1≤ci≤n), where 𝑙𝑖li and 𝑟𝑖ri are are the coordinates of the ends of the 𝑖i-th segment, and 𝑐𝑖ci 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 00.

## [Solution] Multi-Colored Segments solution codeforces

For example, Dmitry has 55 segments:

- The first segment intersects with the second (and these are segments of different colors), so the answers for them are equal to 00.
- For the 33-rd segment, the nearest segment of a different color is the 22-nd segment, the distance to which is equal to 22.
- For the 44-th segment, the nearest segment of a different color is the 55-th segment, the distance to which is equal to 11.
- The 55-th segment lies inside the 22-nd segment (and these are segments of different colors), so the answers for them are equal to 00.

The first line of the input contains an integer 𝑡t (1≤𝑡≤1041≤t≤104) — 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⋅1052≤n≤2⋅105) — the number of segments.

The next 𝑛n lines contain descriptions of the segments. Each segment is described by three integers 𝑙𝑖li, 𝑟𝑖ri and 𝑐𝑖ci (1≤𝑙𝑖≤𝑟𝑖≤109,1≤𝑐𝑖≤𝑛1≤li≤ri≤109,1≤ci≤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 22 segments of different colors.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 2⋅1052⋅105.

## [Solution] Multi-Colored Segments solution codeforces

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.

input

## [Solution] Multi-Colored Segments solution codeforces

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

input

output

0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 1 1 3 0 0 0 2 0 0 2 5 9 1 4

## [Solution] Multi-Colored Segments solution codeforces

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

In the second test case of the first sample there are only 22 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 00.

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 00.

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

In the seventh test case of the first sample, the second segment is a point and is inside the first one, so for both segments the answer is 00.