У Дмитрия есть \(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\).
Выходные данные
Для каждого набора входных данных в отдельной строке выведите \(n\) целых чисел, где \(i\)-е число равно расстоянию от \(i\)-го отрезка до ближайшего отрезка другого цвета.
Примечание
В первом наборе входных данных первого примера есть только один отрезок цвета \(2\), а все остальные отрезки имеют цвет \(1\). Поэтому для отрезков цвета \(1\) ответ равен расстоянию до \(3\)-го отрезка, а для \(3\)-го ответ равен минимальному из расстояний до отрезков цвета \(1\).
Во втором наборе входных данных первого примера есть только \(2\) отрезка, и для них обоих ответ равен расстоянию между ними.
В третьем наборе входных данных первого примера каждый отрезок пересекается хотя бы одним своим концом с отрезком другого цвета, поэтому все ответы равны \(0\).
Четвёртый набор входных данных первого примера разобран в условии.
В пятом наборе входных данных первого примера один отрезок полностью лежит внутри другого, и для них обоих ответ равен \(0\).
В шестом наборе входных данных первого примера все отрезки являются точками разного цвета.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
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
|
|
2
|
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
|