#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int, int>;
constexpr int maxn = 1000000 + 10;
int a[maxn];
vector<pii> l[maxn], r[maxn];
void run(int n, vector<pii> *l)
{
    l[0] = {pii(0, a[0])};
    for (int i=1;i<n;++i)
    {
        vector<pii> u = l[i - 1];
        for (auto &[x, y] : u) ++x, y = (y >> 1) + a[i];
        u.insert(u.begin(), pii(0, a[i]));
        l[i].clear();
        int lst = -1;
        for (auto [x, y] : u) if (y != lst)
        {
            lst = y;
            l[i].emplace_back(pii(x, y));
        }
    }
    for (int i=0;i<n/2;++i) vector<pii>().swap(l[i]);
}
void solve()
{
    int n;
    cin >> n;
    for (int i=0;i<n;++i) cin >> a[i], a[i + n] = a[i];
    run(n + n, l);
    reverse(a, a + n + n);
    run(n + n, r);
    reverse(a, a + n + n);
    for (int i=0;i<n;++i)
    {
        auto &u = l[i + n], &v = r[n + n - 1 - i];
        int ans = a[i];
        for (auto [x, y] : u)
            for (auto [p, q] : v) if (x + p < n) ans = max(ans, y + q - a[i]);
        cout << ans << ' ';
    }
    cout << '\n';
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}