Скоростную автомагистраль Кёнъин, старейшую в Южной Корее, можно разделить на $N$ блоков одинакового размера. Блок $i$ ($1 \le i \le N$) граничит с блоком $i - 1$ слева (за исключением случая $i = 1$) и с блоком $i + 1$ справа (за исключением случая $i = N$).

Чунвун Ким, житель улицы Намбу, решил установить уличные фонари на некоторых блоках. Для каждого блока $i$ Чунвун Ким решает, установить ли фонарь на блоке $i$ и заплатить $W_i$, или не устанавливать его и ничего не платить. После завершения работы каждый блок должен либо иметь установленный фонарь, либо иметь хотя бы одного соседа с установленным фонарем. Общая стоимость работы равна сумме стоимостей установки каждого фонаря.

Рассмотрим все способы, которыми Чунвун Ким может установить фонари, удовлетворяя вышеуказанным условиям. Два способа считаются различными, если существует блок $i$ ($1 \le i \le N$), на котором установлен фонарь в одном способе, но не установлен в другом. Отсортируйте все эти способы по общей стоимости в неубывающем порядке. Затем для заданного $K$ выведите общую стоимость для каждого из первых $K$ способов в этом отсортированном списке. Если для некоторого $x$, где $1 \le x \le K$, существует менее $x$ способов в целом, выведите $-1$ вместо стоимости для этого $x$.

Входные данные

Первая строка содержит два целых числа $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