Задача Q. Border ratio ≡

Условие

Пусть на некотором наборе точек X = {x_i}ni = 1, x_i ∈ R^m задана функция f: R^m↦N. Требуется написать программу, вычисляющую значение border ratio α(x) = ∥x̂ − y∥₂∥ x − y∥₂, ∀ x ∈ X, где y = arg miny ∈ X, f(x) ≠ f(y)∥ x − y∥₂, x̂ = arg minx̂ ∈ X, f(x) = f(x̂)∥x̂ − y∥₂.

Формат входных данных

Первая строка входного файла содержит натуральные числа n, m — количество точек и размерность пространства соответственно. В следующих n строках содержится m вещественных чисел и одно натуральное число — координаты точки и значение функции в этой точке.

Формат выходных данных

Выходной файл должен содержать n вещественных чисел — значения border ratio каждой точки с точностью не менее трёх знаков после запятой.

Ограничения

6 ⩽ n ⩽ 1500

2 ⩽ m ⩽ 50

Примеры тестов

6 2
0 0 0
0 2 1
1 2 0
4 2 1
3 0 1
4 0 0

0.5 1.0 1.0 0.5 1.0 1.0

10 2
0 0 0
0 2 0
4 2 0
6 2 0
4 4 1
6 1 1
6 6 1
0 5 2
0 6 2
0 7 2

0.6 1.0 1.0 1.0 1.0 1.0 0.25 1.0 0.75 0.6