트레이딩 시스템

SY Company는 주식 트레이딩 시스템을 개선하려고 한다. 이를 위해 주가 변동 정보를 활용하기로 한다. 변동값은 연속한 두 날의 주가 차이다. 회사는 어떤 주식의 최근 변동값 n개를 수집한다. 주식의 변동성은 연속한 변동값들의 합 중 최댓값에 크게 영향을 받는다는 사실이 밝혀졌다. 합이 최대가 되는 연속한 변동값들을 찾는 문제는 컴퓨터과학에서 최대 연속 부분합 문제로 알려져 있으며, 입력값은 배열에 저장된다. 최댓값 하나만 이용하는 것보다 k(≥ 1)개의 큰 연속 부분합을 이용하는 것이 트레이딩 시스템 개선에 도움이 된다는 것은 자연스럽다.

주어진 n개의 변동값과 양의 정수 k에 대해, 연속한 변동값들의 합 중 k번째로 큰 것까지를 구하는 프로그램을 작성하시오.

입력은 표준 입력에서 읽는다. 첫 줄에는 두 정수 n과 k가 주어지며, 1 ≤ n ≤ 250,000이고 1 ≤ k ≤ min(10,000, n(n + 1)/2)이다. 다음 줄에는 n개의 변동값을 나타내는 n개의 정수가 주어진다. 모든 변동값은 −109 이상 109 이하이다.

출력은 표준 출력에 쓴다. 정확히 한 줄을 출력한다. 그 줄에는 연속한 변동값들의 합 중 k개를 큰 것부터 작은 순서로 출력한다. 연속 부분합은 하나 이상의 연속한 변동값의 합이다.