캠핑장의 비슷한 받침대

문제

한 캠핑장에서는 공용 장비를 올려놓을 받침대 K개를 골라 새로운 작업 공간을 만들려고 한다. 창고에는 모두 N개의 받침대가 있으며, 각 받침대의 높이는 정수로 기록되어 있다. 같은 높이의 받침대도 여러 개 있을 수 있다. 높이가 같더라도 서로 다른 물건이므로 각각 하나씩 선택할 수 있다. 받침대를 자르거나 다른 물건을 덧대어 높이를 바꿀 수는 없다. 관리자는 선택한 받침대의 높이가 가능한 한 비슷하기를 원한다. 이를 위해 정확히 K개를 선택했을 때 가장 높은 받침대와 가장 낮은 받침대의 높이 차이를 선택의 편차라고 정의한다. 가장 먼저 이 편차가 최소가 되는 선택을 찾아야 한다. 받침대를 창고에서 꺼내는 순서나 원래 놓여 있던 위치는 선택 조건에 영향을 주지 않는다. 입력에서 서로 이웃하지 않은 받침대도 함께 고를 수 있다. 편차가 최소인 선택이 여러 개라면, 그중 가장 낮은 받침대의 높이가 더 작은 선택을 채택한다. 편차와 최저 높이가 모두 같으면 최고 높이도 같으므로, 어떤 실제 받침대를 골랐는지는 구별하지 않는다. 프로그램은 선택한 받침대의 번호나 모든 높이를 출력할 필요가 없다. 최종 편차, 최저 높이, 최고 높이만 순서대로 출력하면 된다. 예를 들어 K가 1이면 어떤 받침대를 골라도 편차는 0이다. 이때에도 같은 동점 규칙을 적용하므로 창고 전체에서 가장 낮은 받침대의 높이가 최저 높이와 최고 높이가 된다. K가 N이면 모든 받침대를 반드시 사용한다. 필요한 개수는 항상 창고에 있는 개수 이하로 주어지므로 선택이 불가능한 경우는 없다. 관리자는 창고 목록의 순서를 바꾸어도 결과가 달라지지 않는 프로그램을 원한다. 주어진 높이 목록으로부터 규칙에 맞는 세 정수를 구한다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ K ≤ N ≤ 100,000이다.
둘째 줄에 N개 받침대의 높이가 공백으로 구분되어 주어진다. 각 높이는 1 이상 1,000,000,000 이하의 정수다.

출력

규칙에 따라 선택했을 때의 편차, 최저 높이, 최고 높이를 공백으로 구분하여 한 줄에 출력한다.

7 3
12 4 9 5 20 10 6

2 4 6

5 2
8 3 8 3 12

0 3 3

4 1
19 7 11 7

0 7 7

출처: Devin.KR 자체 제작