Задача Q. Border ratio

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Пусть на некотором наборе точек X = {xi}ni = 1xiRm задана функция f: RmN. Требуется написать программу, вычисляющую значение border ratio α(x) =  − y2∥ x − y2, ∀ x∈ X, где y = arg miny∈ X, f(x)≠ f(y)∥ x − y2 = arg min∈ X, f(x) = f() − y2.

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

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

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

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

Ограничения

6⩽ n⩽ 1500

2⩽ m⩽ 50

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

Стандартный вход Стандартный выход
1
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
2
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

0.201s 0.035s 13