Задача R. KMeans ≡

Условие

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

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

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

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

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

Ограничения

6 ⩽ n ⩽ 1000

2 ⩽ m, k ⩽ 10

10 ⩽ t ⩽ 10⁹

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

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