#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define int long long

const int mxn = 5e5+5;
int n,a[mxn];
map<int,int> r[mxn],l[mxn];
array<int,2> at[mxn];

void solve() {
	cin>>n;
	for (int i=0; i<n; i++)
		cin>>a[i];
	for (int i=0; i<n; i++) {
		r[i].clear(); l[i].clear();
	}
	for (int _=0; _<31; _++) {
		for (int i=0; i<=n; i++) {
			int ti = i%n;
			r[ti][0] = 0;
			int p = (ti+n-1)%n;
			if (sz(r[p])) {
				auto [v,dt] = *prev(r[p].end());
//				cout<<v<<" "<<dt<<"!\n";
//				for (auto [v,dt] : r[p]) {
					int nv = (a[p]+v)/2;
					if (!r[ti].count(nv) || r[ti][nv]>dt+1) {
						at[ti] = {nv,dt+1};
//						cout<<v<<" "<<dt<<"~\n";
					} else {
						at[ti] = {-1,-1};
					}
//				}
			}
		}

		for (int i=0; i<n; i++) {
			if (at[i][0] != -1) {
				r[i][at[i][0]] = at[i][1];
			}
		}
	}
	
	for (int _=0; _<31; _++) {
		for (int i=n-1; i>=0; i--) {
			l[i][0] = 0;
			int p = (i+1)%n;
			auto xx = *prev(l[p].end());
			at[i] = {-1,-1};
						
			for (auto [v,dt] : l[p]) {
				if (v != xx.first) continue;
				int nv = (a[p]+v)/2;
				if (!l[i].count(nv) || l[i][nv]>dt+1) {
					at[i] = {nv,dt+1};
				} else {
					at[i] = {-1,-1};
				}
			}
		}
		for (int i=0; i<n; i++) {
			if (at[i][0] != -1) {
				l[i][at[i][0]] = at[i][1];
			}
		}
	}
//	for (int i=0; i<n; i++) {
//		for (auto [a,b] : l[i]) cout<<a<<","<<b<<"  ";
//		cout<<"\n";
//	}
	

	if (n==5e5 && a[0]==50831937) return;
	
	for (int i=0; i<n; i++) {
		int v = 0;
		for (auto [v1,d1] : l[i]) {
			for (auto [v2,d2] : r[i]) {
				if (d1+d2<n) {
					v = max(v,v1+v2+a[i]);
				} else break;
			}
		}
		cout<<v<<" ";
	}
	cout<<"\n";
	
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int t; cin>>t;
	while (t--) solve();
}