Optimal Table Placement for Knights

You are given the coordinates of N knights on a 2D plane and are tasked with finding the optimal positions of K tables such that the total sum of the Euclidean distances from each knight to its nearest table is minimized. In other words, you need to partition the knights into K groups and compute the centroid (arithmetic mean) of each group.

The Euclidean distance between two points \((x_1, y_1)\) and \((x_2, y_2)\) is defined as:

[ d((x_1, y_1), (x_2, y_2)) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} ]

This problem can be approached with the k-means clustering algorithm. You are asked to implement the algorithm so that it reads input from stdin and writes the result to stdout in the required format. Each resulting table position (centroid) should be printed on a new line with the x and y coordinates formatted to three decimal places.

inputFormat

The first line of input contains two integers: N and K, where N is the number of knights and K is the number of tables (clusters). This is followed by 2*N integers representing the coordinates of the knights. The coordinates are given in order: x₁ y₁ x₂ y₂ ... x_N y_N.

outputFormat

Output K lines, each containing two floating-point numbers representing the x and y coordinates of a table. The coordinates should be rounded and printed to three decimal places. The order of the tables can be arbitrary.

## sample

6 2
1 3 2 2 3 1 8 8 9 9 10 10

2.000 2.000
9.000 9.000

</p>