Equal-Size Interval Clustering

You are given the coordinates of N sheep on a plane. Sort the sheep lexicographically by (x, y): first by increasing x, and if two sheep have the same x, by increasing y.

Keeping this sorted order, split the sheep into K non-empty consecutive groups. The group sizes must be as equal as possible. Let q = floor(N / K) and r = N mod K. The first r groups contain q + 1 points each, and the remaining groups contain q points each.

Treat each group as one cluster. For every cluster, output the arithmetic mean of the coordinates of the points in that cluster. Output the centers in the order the groups are created.

The first line contains two positive integers N and K, the number of sheep and the number of clusters.

Each of the next N lines contains two integers Xi Yi, the coordinates of one sheep.

Print K lines. On the ith line, print the x and y coordinates of the ith cluster center, separated by a space.

Print every coordinate with exactly six digits after the decimal point.

• 1 <= K < N <= 1000
• 1 <= K <= 100
• 0 <= Xi, Yi <= 10000
• All input coordinates are integers.