시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 1536 MB 61 20 12 36.364%

문제

서울의 남부를 잇는 남부순환로 는 $N$ 개의 크기가 같은 블록 으로 나눌 수 있다. $i$번 블록 ($1 \leq i \leq N$)의 왼쪽에는 $i - 1$ 번 블록이 존재하며 ($i = 1$ 일 때를 제외), 오른쪽에는 $i + 1$ 번 블록이 존재한다 ($i = N$ 일 때를 제외). 이름이 순환로이지만, $N$ 번 블록의 오른쪽에 $1$ 번 블록이 인접하지 않음에 유의하라.

남부순환로에는 가로등이 전혀 설치되어 있지 않아서, 밤이 되면 어둡고 이상한 기운이 도는 것으로 악명이 높다. 이 문제를 해결하기 위해, 남부순환로1119길 주민 김준원은 몇 개의 블록에 가로등을 설치하기로 했다. 

가로등을 설치할 때, 김준원은 $N$ 개의 블록에 대해서 하나의 가로등을 설치할지 말지를 결정한다. 만약 $i$ 번 블록에 가로등을 설치하기로 결정하였다면, 김준원은 $W_i$ 의 비용을 들여 가로등을 설치한다. 설치하지 않기로 결정하였다면, 비용이 부과되지 않는다. 작업이 끝난 이후, 모든 블록은 가로등이 설치되어 있거나, 왼쪽 / 오른쪽에 인접한 블록에 가로등이 설치되어 있어야 한다. 작업의 전체 비용 은 각 가로등을 설치하는 데 든 비용의 합이다. 

김준원이 위 조건을 만족시키면서 가로등을 설치하는 모든 경우를 생각해 보자. 두 경우가 다르다는 것은 어떠한 블록 $1 \le i \le N$ 이 존재하여 한 경우에는 $i$ 번 블록에 가로등이 있고, 다른 경우에는 가로등이 없음을 뜻한다. (즉, 자신 또는 인접한 블록에 가로등이 설치되어 있어야 한다는 조건을 무시하면 모든 경우는 $2^N$ 가지가 있다.) 이 모든 경우를 전체 비용이 감소하지 않는 순서대로 정렬하였을 때, 모든 $1 \le i \le K$ 에 대해, 정렬된 배열의 $i$ 번째 원소의 전체 비용들을 모두 출력하라. 만약 경우의 수가 $i$ 미만이라면, -1을 출력하라.

입력

첫 번째 줄에 두 정수 $N, K$가 공백으로 구분되어 주어진다. ($1 \le N, K \le 250\,000$)

두 번째 줄에 $N$ 개의 정수 $W_1, W_2 \cdots W_N$가 공백으로 구분되어 주어진다. $W_i$ 는 $i$번 블록에 가로등을 설치하는 데 필요한 비용이다. ($0 \leq W_i \leq 10^9$)

출력

$K$ 개의 줄을 출력한다. 이 중 $i$ 번째 줄에는, 정렬된 배열의 $i$ 번째 원소의 전체 비용을 출력하라. 만약 경우의 수가 $i$ 미만이라면, -1을 출력하라.

예제 입력 1

5 3
1 3 10 3 1

예제 출력 1

4
4
5

예제 입력 2

12 20
317 448 258 208 284 248 315 367 562 500 426 390

예제 출력 2

1525
1566
1602
1616
1633
1652
1697
1725
1730
1733
1747
1761
1764
1766
1773
1775
1783
1792
1811
1824

예제 입력 3

3 9
0 0 0

예제 출력 3

0
0
0
0
0
-1
-1
-1
-1

출처

Contest > Good Bye, BOJ > Good Bye, BOJ 2020! I번