I-变大！_2020 CCPC Wannafly Winter Camp Day6 Div.1＆2（重现赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给一个序列 ${a[1...n]}$ ，你每次可以选择一个 $i(2\leq i<n)$ ，然后将 ${a[i-1],a[i],a[i+1]}$ 全变成 ${max(a[i-1],a[i],a[i+1])}$
你可以进行 ${k}$ 次这样的操作，目标是最大化 $\displaystyle \sum_{i=1}^{n}a[i]$ ，求最后的答案。

你需要对 ${k=1...n}$ 都输出答案。

输入描述:

第一行一个正整数  表示数据组数
对于每组数据，第一行一个正整数  表示序列长度，第二行  个正整数表示 
，，

输出描述:

对于每组数据，输出一行  个数，第  个数表示  的答案

示例1

输入

复制

输出

复制

18 25 25 25 25
28 35 35 35 35