버스 노선 공동 안내 구간

문제

한 버스 터미널은 여러 노선의 출발 위치를 긴 안내판 위에 표시한다. 안내판에는 왼쪽 끝을 기준으로 한 정수 좌표가 적혀 있으며, 각 노선에는 출발 위치를 나타내는 좌표 하나가 배정되어 있다. 서로 다른 노선이 같은 위치를 함께 사용할 수 있으므로 같은 좌표가 여러 번 주어질 수 있다. 터미널은 이 가운데 정확히 K개 노선을 골라 공동 안내 띠를 설치하려 한다. 안내 띠는 선택한 노선의 좌표를 모두 포함하는 하나의 닫힌 구간이다. 선택하지 않은 노선의 좌표가 그 구간 안에 들어 있어도 상관없다. 구간 안에 있는 모든 노선을 선택해야 하는 것은 아니며, 어떤 노선을 선택했는지는 안내 띠의 길이를 계산할 때만 사용한다. 선택한 K개 좌표 중 가장 작은 값을 L, 가장 큰 값을 R이라고 하자. 이 선택에 필요한 안내 띠는 구간 [L, R]이고, 길이는 R-L이다. 양 끝의 좌표도 구간에 포함된다. 같은 좌표를 가진 노선만 K개 선택할 수 있다면 길이가 0인 안내 띠도 만들 수 있다. K가 1이면 선택한 노선 하나의 좌표가 양 끝이 된다. 담당자는 먼저 안내 띠의 길이를 가능한 한 짧게 만들려 한다. 가장 짧은 길이를 만드는 구간이 여러 개라면 왼쪽 끝 좌표 L이 가장 작은 구간을 사용한다. 길이와 왼쪽 끝이 모두 같으면 오른쪽 끝도 같으므로, 실제로 어느 노선들을 골랐는지는 구분하지 않는다. 입력에서 먼저 나온 노선을 우선하는 규칙도 없다. 노선의 입력 순서는 안내판에서의 좌우 순서와 관계가 없다. 모든 노선의 좌표를 이용하여 조건에 맞는 안내 띠의 길이와 양 끝 좌표를 구해야 한다. K는 전체 노선 수 이하이므로 선택할 수 없는 경우는 없다. 출력에는 선택한 노선의 번호나 구간 내부의 다른 좌표를 포함하지 않는다.

입력

첫째 줄에 노선 수 N과 선택할 노선 수 K가 공백으로 구분되어 주어진다. N과 K는 1 ≤ K ≤ N ≤ 40,000을 만족하는 정수이다.
둘째 줄에 각 노선의 좌표를 나타내는 N개의 정수 x가 공백으로 구분되어 주어진다. 각 좌표는 0 이상 99,999 이하이다. 같은 좌표가 여러 번 주어질 수 있다.

출력

조건에 맞는 안내 띠의 길이, 왼쪽 끝 좌표 L, 오른쪽 끝 좌표 R을 공백으로 구분하여 한 줄에 출력한다. 길이가 같으면 L이 가장 작은 구간을 출력한다.

6 3
18 4 11 5 20 9

5 4 9

5 2
8 3 8 3 12

0 3 3

4 1
17 6 22 9

0 6 6

출처: Devin.KR 자체 제작