남부순환로

서울의 남부를 잇는 남부순환로 는 $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을 출력하라.