Элси учится рисовать. У нее есть холст из \(n\) клеток, пронумерованных от \(1\) до \(n\), и она может раскрасить любое (возможно, пустое) подмножество клеток.
У Элси есть двумерный массив \(a\), который она будет использовать для оценки картин. Пусть максимальные непрерывные отрезки закрашенных клеток в картине равны \([l_1,r_1],[l_2,r_2],\ldots,[l_x,r_x]\). Красота картины — это сумма \(a_{l_i,r_i}\) по всем \(1 \le i \le x\). На изображении выше максимальные непрерывные отрезки закрашенных клеток равны \([2,4],[6,6],[8,9]\), а красота картины равна \(a_{2,4}+a_{6,6}+a_{8,9}\).
Всего есть \(2^n\) различных способов раскрасить холст. Помогите Элси найти \(k\) наибольших значений красоты картины, которые она может получить, среди всех способов. Обратите внимание, что эти \(k\) значений не обязательно должны быть различными. Гарантируется, что существует не менее \(k\) различных способов раскрасить холст.
Выходные данные
Для каждого набора входных данных выведите в отдельной строке \(k\) целых чисел: \(i\)-е из них должно равняться \(i\)-му наибольшему значение красоты картины, которое может получить Элси.
Примечание
В первом наборе входных данных Элси может либо закрасить единственную клетку, либо не закрашивать ее. Если она раскрасит единственную клетку, красота картины составит \(-5\). Если она решит не раскрашивать ее, красота картины составит \(0\). Таким образом, наибольшая красота, которую она может получить, равна \(0\), а вторая по величине красота, которую она может получить, равна \(-5\).
Ниже приведена иллюстрация третьего набора входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2
-5
2 4
2 -3
-1
3 8
2 4 3
1 3
5
6 20
0 -6 -3 0 -6 -2
-7 -5 -2 -3 -4
7 0 -9 -4
2 -1 1
1 -2
-6
|
0 -5
2 0 -1 -3
7 5 4 3 3 2 1 0
8 8 7 7 5 5 2 2 1 1 1 1 1 1 0 0 0 0 0 -1
|