균등 구간 클러스터링

평면 위에 있는 양 N마리의 좌표가 주어진다. 양들을 (x, y) 좌표의 사전순, 즉 x가 작은 순서로 정렬하고 x가 같으면 y가 작은 순서로 정렬한다.

정렬된 순서를 유지한 채 양들을 K개의 비어 있지 않은 연속 구간으로 나눈다. 구간의 크기는 가능한 한 같아야 한다. q = floor(N / K), r = N mod K라고 하면, 앞의 r개 구간은 각각 q + 1개의 점을 가지고 나머지 구간은 각각 q개의 점을 가진다.

각 구간을 하나의 클러스터로 보고, 그 클러스터에 속한 점들의 산술평균 좌표를 클러스터 중심으로 출력하라. 중심은 구간이 만들어지는 순서대로 출력한다.

첫째 줄에 양의 수 N과 클러스터의 수 K가 공백으로 구분되어 주어진다.

다음 N개의 줄에는 각 양의 좌표 Xi Yi가 공백으로 구분되어 주어진다.

K개의 줄을 출력한다. i번째 줄에는 i번째 클러스터 중심의 x좌표와 y좌표를 공백으로 구분하여 출력한다.

각 좌표는 소수점 아래 정확히 여섯 자리까지 출력한다.

• 1 <= K < N <= 1000
• 1 <= K <= 100
• 0 <= Xi, Yi <= 10000
• 입력의 모든 좌표는 정수이다.