대한민국에서 가장 오래된 고속도로인 경인고속도로는 동일한 크기의 $N$개의 블록으로 나눌 수 있다. 블록 $i$ ($1 \le i \le N$)의 왼쪽에는 블록 $i - 1$이 있고 ($i = 1$인 경우는 제외), 오른쪽에는 블록 $i + 1$이 있다 ($i = N$인 경우는 제외).

남부순환로 1119길에 거주하는 김준운은 여러 블록에 가로등을 설치하기로 했다. 각 블록 $i$에 대해, 김준운은 블록 $i$에 가로등을 설치하고 $W_i$의 비용을 지불할지, 아니면 설치하지 않고 비용을 지불하지 않을지 결정한다. 작업이 완료된 후, 모든 블록은 가로등이 설치되어 있거나, 적어도 하나의 이웃 블록에 가로등이 설치되어 있어야 한다. 작업의 총비용은 설치된 각 가로등의 비용의 합이다.

위의 조건을 만족하면서 김준운이 가로등을 설치하는 모든 방법을 고려해 보자. 두 방법은 어떤 블록 $i$ ($1 \le i \le N$)에 대해 한 방법에는 가로등이 설치되어 있고 다른 방법에는 설치되어 있지 않다면 서로 다른 것으로 간주한다. 이러한 모든 방법을 총비용을 기준으로 오름차순으로 정렬한다. 주어진 $K$에 대해, 정렬된 리스트에서 처음 $K$개 방법 각각의 총비용을 출력한다. 만약 $1 \le x \le K$인 어떤 $x$에 대해 전체 방법의 수가 $x$개 미만이라면, 해당 $x$에 대해서는 $-1$을 출력한다.

입력

첫 번째 줄에는 블록의 수 $N$과 출력할 방법의 수 $K$가 주어진다 ($1 \le N, K \le 2.5 \cdot 10^5$).

두 번째 줄에는 각 블록에 가로등을 설치하는 비용인 $N$개의 정수 $W_1, W_2, \dots, W_N$이 주어진다 ($0 \le W_i \le 10^9$).

출력

$K$개의 줄을 출력한다. $i$번째 줄에는 정렬된 리스트에서 $i$번째로 비용이 적은 가로등 설치 방법의 총비용을 출력한다. 만약 방법의 수가 $i$보다 작다면, 대신 $-1$을 출력한다.

예제

예제 1

5 3
1 3 10 3 1

4
4
5

예제 2

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

1525

예제 3

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

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

예제 4

3 9
0 0 0

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