import sys readline = sys.stdin.readline N, K = map(int, readline().split()) A = list(map(int, readline().split())) INF = 10**9+7 De = [[-INF]*(N+1) for _ in range(N)] dpl = [[[-INF]*(t+1) for _ in range(N)] for t in range(K)] dpr = [[[-INF]*(t+1) for _ in range(N)] for t in range(K)] for i in range(N): dpl[0][i][0] = K*A[i] dpr[0][i][0] = K*A[i] for t in range(0, K-1): for l in range(N): for lp in range(min(t+1, N-l)): r = l + lp + 1 if dpl[t][l][lp] == -INF: continue dl = dpl[t][l][lp] dr = dpr[t][l][lp] if t+2 < K and l+1 != r: dpl[t+2][l][lp] = max(dpl[t+2][l][lp], dl) dpr[t+2][l][lp] = max(dpr[t+2][l][lp], dr) if l != 0: dpl[t+1][l-1][lp+1] = max(dpl[t+1][l-1][lp+1], dl+(K-1-t)*A[l-1]) if r != N: dpr[t+1][l][lp+1] = max(dpr[t+1][l][lp+1], dr+(K-1-t)*A[r]) if t < t+r-l-1 < K: dpl[t+r-l-1][l][lp] = max(dpl[t+r-l-1][l][lp], dr) dpr[t+r-l-1][l][lp] = max(dpr[t+r-l-1][l][lp], dl) if l+1 != r: if (K-t)&1: De[l][min(l+K-t, r)] = max(De[l][min(l+K-t, r)], dl) else: De[l+1][min(l+K-t, r)] = max(De[l+1][min(l+K-t, r)], dl) if l <= r-K+t: De[r-K+t][r] = max(De[max(l, r-K+t)][r], dr) else: if (r-K+t-l)%2 == 0: De[l][r] = max(De[l][r], dr) else: De[l+1][r] = max(De[l+1][r], dr) ans = [-INF]*N for l in range(N): for lp in range(min(K, N-l)): r = l + lp + 1 ans[l] = max(ans[l], dpl[K-1][l][lp]) ans[r-1] = max(ans[r-1], dpr[K-1][l][lp]) for l in range(N): for r in range(l+1, N+1): d = De[l][r] for i in range(l, r, 2): ans[i] = max(ans[i], d) Ans = [-INF]*N for i in range(N): if i > 0: Ans[i-1] = max(Ans[i-1], ans[i]) if i < N-1: Ans[i+1] = max(Ans[i+1], ans[i]) print('\n'.join(map(str, Ans)))