은행 창구의 안내 구간

문제

은행 창구에서는 다음 업무 시간에 처리할 현금 인출 신청서를 정리하고 있다. 신청서는 모두 N장이며, 각 신청서에는 고객이 인출하려는 금액이 적혀 있다. 신청 금액은 모두 양의 정수다. 같은 금액이 적힌 신청서도 서로 다른 신청서로 취급한다. 창구 담당자는 이번 업무 시간에 정확히 K장의 신청서를 처리한다. 신청서를 고르는 순서는 자유로우며, 입력된 순서대로 고를 필요는 없다. 고른 신청서를 처리할 때 고객에게 보여 줄 안내판에는 두 정수 L과 U를 적는다. L은 고른 신청서의 금액 중 최솟값이고, U는 그중 최댓값이어야 한다. 안내판은 이번에 처리하는 신청 금액이 L 이상 U 이하라는 뜻이다. 담당자는 안내판에 표시되는 금액의 폭인 U-L을 최대한 작게 만들려고 한다. 폭이 작으면 해당 업무 시간에 준비할 지폐 구성을 더 좁은 범위에 맞출 수 있기 때문이다. 가능한 선택 중 U-L이 가장 작은 안내 구간을 구해야 한다. 최소 폭을 만드는 안내 구간이 여러 개라면 L이 가장 작은 구간을 선택한다. 폭과 L이 같으면 U도 같으므로 추가적인 동점 처리는 필요하지 않다. 안내 구간 안에 금액이 들어가는 신청서를 모두 처리해야 하는 것은 아니다. 선택한 신청서는 정확히 K장이고, 나머지 신청서는 같은 금액이 적혀 있더라도 다음 업무 시간으로 넘길 수 있다. 또한 고른 신청서 자체나 처리 순서는 출력하지 않는다. 최종 안내판에 적을 L과 U만 출력한다. K는 1 이상 N 이하이므로 신청서를 고르는 방법은 항상 존재한다. K가 1이거나 같은 금액의 신청서를 K장 고를 수 있다면 안내 구간의 폭은 0이 될 수 있다.

입력

첫째 줄에 두 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ K ≤ N ≤ 200,000이다.
둘째 줄에 각 신청서의 인출 금액을 나타내는 N개의 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 1 ≤ A_i ≤ 1,000,000,000이다.

출력

조건에 따라 선택한 안내 구간의 최솟값 L과 최댓값 U를 공백으로 구분하여 한 줄에 출력한다. 두 값은 모두 정수로 출력한다.

7 3
18 7 11 8 19 12 9

7 9

6 4
25 25 41 25 25 41

25 25

5 1
34 16 28 16 52

16 16

출처: Devin.KR 자체 제작