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)] Do = [[-INF]*(N+1) for _ in range(N)] dpl = [[[-INF]*(N+1) for _ in range(N)] for _ in range(K)] dpr = [[[-INF]*(N+1) for _ in range(N)] for _ in range(K)] for i in range(N): dpl[0][i][i+1] = K*A[i] dpr[0][i][i+1] = K*A[i] for t in range(0, K-1): for l in range(N): for r in range(l+1, min(l+t+2, N+1)): if dpl[t][l][r] == -INF: continue dl = dpl[t][l][r] dr = dpr[t][l][r] if t+2 < K and l+1 != r: dpl[t+2][l][r] = max(dpl[t+2][l][r], dl) dpr[t+2][l][r] = max(dpr[t+2][l][r], dr) if l != 0: dpl[t+1][l-1][r] = max(dpl[t+1][l-1][r], dl+(K-1-t)*A[l-1]) if r != N: dpr[t+1][l][r+1] = max(dpr[t+1][l][r+1], dr+(K-1-t)*A[r]) if t < t+r-l-1 < K: dpl[t+r-l-1][l][r] = max(dpl[t+r-l-1][l][r], dr) dpr[t+r-l-1][l][r] = max(dpr[t+r-l-1][l][r], 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: Do[l][min(l+K-t, r)] = max(Do[l][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 ((K-t)&1)^((r-l)&1): De[max(l, r-K+t)][r] = max(De[max(l, r-K+t)][r], dr) else: Do[max(l, r-K+t)][r] = max(Do[max(l, r-K+t)][r], dr) ans = [-INF]*N for l in range(N): for r in range(l+1, N+1): ans[l] = max(ans[l], dpl[K-1][l][r]) ans[r-1] = max(ans[r-1], dpr[K-1][l][r]) 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) d = Do[l][r] for i in range(l+1, 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)))