Задача R. KMeans

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

Условие

Пусть задан некоторый набор точек X = {xi}ni = 1xiRm. Требуется выполнить кластеризацию точек на k кластеров, используя наивный алгоритм KMeans.

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

Первая строка входных данных содержит натуральные числа n, m, k, t — количество точек, размерность пространства, количество кластеров и максимальное количество итераций соответственно. В каждой из следующих n строк содержится m вещественных чисел и одно натуральное число — координаты точки и начальное значение кластера точки. Значения кластеров нумеруются от 0 до k − 1.

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

Выходной данные должны содержать n натуральных чисел — номер кластера каждой точки.

Ограничения

6⩽ n⩽ 1000

2⩽ m, k⩽ 10

10⩽ t⩽ 109

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

Стандартный вход Стандартный выход
1
6 2 2 10
0 0 0
0 3 1
3 0 1
2 5 0
5 2 0
5 5 1
0
0
0
1
1
1

0.090s 0.014s 13