#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=5e5+5;
int ans[2][N][35][2],n,a[N],T,cnt[2][N],v;
void cl(int i,int j,int v){
	ans[v][i][1][0]=1;
	ans[v][i][1][1]=a[i];
	cnt[v][i]=1; 
	for(int k=1;k<=cnt[v][j];k++){
		if(ans[v][j][k][1]/2+a[i]!=ans[v][i][cnt[v][i]][1]){
			cnt[v][i]++;
			ans[v][i][cnt[v][i]][0]=ans[v][j][k][0]+1;
			ans[v][i][cnt[v][i]][1]=ans[v][j][k][1]/2+a[i];
		}
	}
}
void cl(int v){
	cl(1,n,v);
	for(int i=2;i<=n;i++) cl(i,i-1,v);
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]),cnt[0][i]=cnt[1][i]=0;
		if(n==1){
			printf("%d\n",a[1]);
			continue;
		}
		cl(0);
		cl(0);
		v=(n+1)/2;
		for(int i=1;i<=n/2;i++) swap(a[i],a[n-i+1]);
		cl(1);
		cl(1);
		for(int i=1;i<=n;i++){
			int an=0,j=1;
			while(ans[0][i][j][0]<=n+1 && j<cnt[0][i]) j++;
			an=ans[0][i][j][1];
			for(int k=1;k<=cnt[1][n-i+1];k++){
				while(ans[0][i][j][0]+ans[1][n-i+1][k][0]>n+1 && j) j--;
				if(!j) an=max(an,ans[1][n-i+1][k][1]);
				else an=max(an,ans[0][i][j][1]+ans[1][n-i+1][k][1]-a[n-i+1]);
			}
			printf("%d ",an);
		}
		printf("\n");
	}
	return 0;
}