F. Разноцветные отрезки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Дмитрия есть $$$n$$$ разноцветных отрезков на координатной прямой $$$Ox$$$. Каждый отрезок характеризуется тремя целыми числами $$$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$$$.
  • Для $$$3$$$-го отрезка ближайший к нему отрезок другого цвета — это $$$2$$$-й, расстояние до которого равно $$$2$$$.
  • Для $$$4$$$-го отрезка ближайший к нему отрезок другого цвета — это $$$5$$$-й, расстояние до которого равно $$$1$$$.
  • $$$5$$$-й отрезок лежит внутри $$$2$$$-го (и это отрезки разных цветов), поэтому ответы для них равны $$$0$$$.
Входные данные

Первая строка входных данных содержит целое число $$$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$$$-го отрезка, а также цвет этого отрезка. Гарантируется, что есть хотя бы $$$2$$$ отрезка разного цвета.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных в отдельной строке выведите $$$n$$$ целых чисел, где $$$i$$$-е число равно расстоянию от $$$i$$$-го отрезка до ближайшего отрезка другого цвета.

Примеры
Входные данные
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
Выходные данные
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
Входные данные
4
8
11 16 7
12 15 7
2 5 8
17 22 5
1 8 8
19 23 8
16 16 6
6 7 5
9
1 4 3
5 11 1
8 11 3
1 10 1
2 11 1
1 10 4
3 11 1
5 7 1
1 11 1
9
25 25 1
26 26 1
24 24 2
13 14 2
12 16 2
17 18 1
19 19 1
24 27 2
24 27 1
9
15 18 1
20 22 2
13 22 2
13 22 2
3 13 2
6 10 2
3 6 2
19 24 2
22 24 2
Выходные данные
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
Примечание

В первом наборе входных данных первого примера есть только один отрезок цвета $$$2$$$, а все остальные отрезки имеют цвет $$$1$$$. Поэтому для отрезков цвета $$$1$$$ ответ равен расстоянию до $$$3$$$-го отрезка, а для $$$3$$$-го ответ равен минимальному из расстояний до отрезков цвета $$$1$$$.

Во втором наборе входных данных первого примера есть только $$$2$$$ отрезка, и для них обоих ответ равен расстоянию между ними.

В третьем наборе входных данных первого примера каждый отрезок пересекается хотя бы одним своим концом с отрезком другого цвета, поэтому все ответы равны $$$0$$$.

Четвёртый набор входных данных первого примера разобран в условии.

В пятом наборе входных данных первого примера один отрезок полностью лежит внутри другого, и для них обоих ответ равен $$$0$$$.

В шестом наборе входных данных первого примера все отрезки являются точками разного цвета.