Chef likes arrays a lot. Today, he found an array A consisting of N positive integers.
Let L denote the sorted (in non-increasing order) list of size N*(N+1)/2 containing the sums of all possible contiguous subarrays of A. Chef is interested in finding the first K elements from the list L. Can you help him in accomplishing this task?

Input
There is only a single test case per input file.
The first line of input contains two space separated integer numbers N and K denoting the size of the array and the number of the maximal sums you need to find.
The following line contains N space separated integer numbers denoting the array A.

Output
Output K space separated integers where the i^th integer denotes the i^th element of L.

Constraints


1 ≤ N ≤ 10^5


1 ≤ K ≤ min(N*(N+1)/2, 10^5)


1 ≤ Ai ≤ 10^9



Example

Input 1
3 4
1 3 4

Output 1
8 7 4 4

Input 2
3 3
10 2 7

Output 2
19 12 10

Explanation
Test 1:


The first 4 elements of it are [8, 7, 4, 4].
import heapq


def solver(N, K, A):
    ans, heap = [], []
    prefix = [A[0]]
    for x in A[1:]:
        prefix.append(prefix[-1] + x)

    indexMap = set()
    heapq.heappush(heap, (-prefix[-1], 0, N - 1))
    indexMap.add((0, N - 1))

    while K > 0 and len(heap) != 0:
        val, i, j = heapq.heappop(heap)
        val = -val
        ans.append(val)
        if i != j:
            if (i + 1, j) not in indexMap:
                heapq.heappush(heap, (-(val - A[i]), i + 1, j))
                indexMap.add((i + 1, j))

            if (i, j - 1) not in indexMap:
                heapq.heappush(heap, (-(val - A[j]), i, j - 1))
                indexMap.add((i, j - 1))

        K -= 1
    return ans


if __name__ == '__main__':
    N, K = map(int, raw_input().split())
    A = map(int, raw_input().split())

    print ' '.join([str(i) for i in solver(N, K, A)])