스마트 홈의 공통 보정 범위

문제

스마트 홈 관리기는 집 안에 설치된 센서들을 묶어 공통 보정 설정을 배포하려 한다. 각 센서는 공장에서 측정한 보정 지표를 하나 가지고 있다. 보정 지표는 정수이며, 서로 다른 센서가 같은 지표를 가질 수도 있다. 같은 지표를 가진 센서들도 각각 별개의 장치로 센다. 관리기는 이번 배포에서 정확히 K개의 센서를 선택해야 한다. 센서를 선택하면 그 센서들에 사용할 공통 보정 범위가 자동으로 정해진다. 선택한 센서의 지표 중 최솟값을 A, 최댓값을 B라고 할 때, 공통 보정 범위는 양 끝을 포함한 A부터 B까지다. 관리자가 범위의 양 끝을 별도로 지정하거나 선택한 센서의 지표를 바꾸는 것은 허용하지 않는다. 보정 범위의 폭은 B-A다. 선택한 센서들의 지표가 모두 같다면 폭은 0이다. 범위 안에 있는 모든 센서를 반드시 선택해야 하는 것은 아니다. 예를 들어 같은 지표를 가진 센서가 여러 개 있더라도 그중 일부만 선택할 수 있으며, 선택하지 않은 센서는 이번 배포에서 제외된다. 입력에서 센서가 나열된 순서는 선택 가능 여부와 관계없다. 관리기는 공통 설정의 오차를 줄이기 위해 범위의 폭이 가장 작아지도록 센서를 선택하려 한다. 최소 폭을 만드는 선택이 여러 개라면 범위의 시작값 A가 가장 작은 것을 사용한다. 폭과 시작값이 모두 같으면 끝값 B도 같으므로, 어떤 센서를 선택했는지는 구분하지 않는다. 센서 수와 선택할 센서 수는 조건을 만족하므로 선택이 불가능한 경우는 없다. 위 기준에 따라 정해지는 범위의 폭, 시작값, 끝값을 구한다. 선택한 센서의 번호는 출력하지 않는다.

입력

첫째 줄에 정수 N과 K가 주어진다. 1 ≤ K ≤ N ≤ 20,000이다.
둘째 줄에 각 센서의 보정 지표를 나타내는 정수 X_1, X_2, …, X_N이 공백으로 구분되어 주어진다. 0 ≤ X_i ≤ 100,000,000이다.

출력

선택 기준에 따른 최소 폭 B-A, 범위의 시작값 A, 범위의 끝값 B를 공백으로 구분하여 한 줄에 출력한다.

6 3
18 4 11 7 12 20

5 7 12

5 2
9 3 9 3 15

0 3 3

4 1
8 0 6 2

0 0 0

출처: Devin.KR 자체 제작