import java.util.*;
import java.io.*;

public class Kmeans {

	static double[][] X;
	static int[][] Y;
	static double centers[][];
	static int[] clusterlabels;
	static int[] clustersize;
	static int nolabels, nofeatures, noexamples, kcenters, noclusterings;

	public static void initalization() {
		Random generator = new Random();
		boolean[] mark = new boolean[noexamples];
		for (int i=0; i<noexamples; i++)
			mark[i] = false;
		int r;
		centers = new double[kcenters][nofeatures];
		for (int i=0; i<kcenters; i++) {
			while (true) {
				r = generator.nextInt(noexamples);
				if (mark[r]==false)
					break;
			}
			for (int j=0; j<nofeatures; j++)
				centers[i][j] = X[r][j];
		}
	}

	public static void recompute_centers() {
		centers = new double[kcenters][nofeatures];
		for (int i=0; i<noexamples; i++)
			for (int j=0; j<nofeatures; j++)
				centers[clusterlabels[i]][j] +=  X[i][j];
		for (int i=0; i<kcenters; i++)
			for (int j=0; j<nofeatures; j++)
				centers[i][j] /= clustersize[i];
	}

	public static int find_cluster_labels(int ex) {
		double min_obj = Double.MAX_VALUE;
		int min_cluster=0;
		double temp;
		for (int i=0; i<kcenters; i++) {
			temp = 0;
			for (int j=0; j<nofeatures; j++)
				temp += (centers[i][j]-X[ex][j])*(centers[i][j]-X[ex][j]);
			if (temp < min_obj) {
				min_cluster = i;
				min_obj = temp;
			}
		}
		return min_cluster;
	}

	public static boolean assign_clustering_labels() {
		boolean flag = false;
		int temp;
		clustersize = new int[kcenters];
		for (int i=0; i<noexamples; i++) {
			temp = find_cluster_labels(i);
			if (temp != clusterlabels[i])
				flag = true;
			clusterlabels[i] = temp;
			clustersize[temp]++;
		}
		return flag;
	}

	public static void kmean() {
		initalization();
		clusterlabels = new int[noexamples];
		for (int i=0; i<noexamples; i++)
			clusterlabels[i] = -1;
		while (true) {
			if (!assign_clustering_labels())
				break;
			recompute_centers();
			System.err.print(".");
		}
		System.err.println();

		for (int i=0; i<noexamples; i++)
			System.out.print((clusterlabels[i]+1) + " ");
		System.out.println();
	}	

	public static void main(String[] args) {
                if (args.length != 3) {
                        System.err.println("Usage: java Kmeans file kcenters noclusterings");
                        System.exit(1);
                }
		String file = args[0];
		kcenters = Integer.parseInt(args[1]);
		noclusterings = Integer.parseInt(args[2]);

                System.err.print("Reading in " + file + ":");
                try {
                        BufferedReader in = new BufferedReader(new FileReader(file));
			String str;
			String[] seq;
			str = (in.readLine()).trim();
			seq = str.split(" ");
			noexamples = Integer.parseInt(seq[0]);
			nofeatures = Integer.parseInt(seq[1]);
			nolabels = Integer.parseInt(seq[2]);
			X = new double[noexamples][nofeatures];
			Y = new int[noexamples][nolabels];
			for (int i=0; i<noexamples; i++) {
				str = (in.readLine()).trim();
				seq = str.split(" ");

				for (int j=0; j<nolabels; j++)
					Y[i][j] = Integer.parseInt(seq[j]);
				
				for (int j=nolabels; j<seq.length; j++)
					X[i][j-nolabels] = Double.parseDouble(seq[j]);
				System.err.print(".");
                        }
                        in.close();
                } catch (IOException e) {
                        System.err.print("Can not read " + file + " containing sequence data !!!\n");
                }
		System.err.println("Done reading data.");
		for (int i=0; i<noclusterings; i++)
			kmean();
	}

}
