#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#pragma GCC optimize("O3")

const int N = 11000000;
const int X = 32100;

array<int, 2> B[N], Bt[N];
vector<int> C;
ll pref[N];
int cnt[X];

vector<int> solve(vector<int> A) {
    int n = A.size();
    if (is_sorted(begin(A), end(A))) {
        for (int i = 0; i < n; i++)
            B[i] = {A[i], i};
    } else {
        for (int i = 0; i < n; i++)
            cnt[A[i] % X]++;
        for (int i = 0; i + 1 < X; i++)
            cnt[i + 1] += cnt[i];
        for (int i = n - 1; i >= 0; i--)
            Bt[--cnt[A[i] % X]] = {A[i], i};
        for (int i = 0; i < X; i++)
            cnt[i] = 0;
        for (int i = 0; i < n; i++)
            cnt[A[i] / X]++;
        for (int i = 0; i + 1 < X; i++)
            cnt[i + 1] += cnt[i];
        for (int i = n - 1; i >= 0; i--)
            B[--cnt[Bt[i][0] / X]] = Bt[i];
        for (int i = 0; i < X; i++)
            cnt[i] = 0;
    }
    int L = 0, R = 0;
    ll S = accumulate(begin(A), end(A), 0ll), cur = 0;
    while (R < n && cur + B[R][0] <= S / 2) {
        cur += B[R][0];
        R++;
    }
    L = n - R;
    if (cur != S / 2)
        L--;
    reverse(B, B + R);
    reverse(B + R, B + n);
    for (int i = 0; i < n; i++)
        pref[i] = (i == 0 ? 0 : pref[i - 1]) + B[i][0];
    auto cnt = [&](int k) -> int {
        auto get = [&](int i) -> ll {
            if (i < k) return pref[i];
            if (i < k + n - R) return pref[i - k + R] - (R == 0 ? 0 : pref[R - 1]) + pref[k - 1];
            return pref[n - 1] - (R == 0 ? 0 : pref[R - 1]) + pref[i - n + R];
        };
        int l = -1, r = n;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (get(m) <= S / 2) l = m;
            else r = m;
        }
        return r;
    };
    int v = n / 2;
    v = max(v, L);
    v = min(v, R);
    int l = 0, r = R + 1;
    while (r - l > 1) {
        int k = (l + r) / 2;
        if (cnt(k) <= v) l = k;
        else r = k;
    }
    int k = l;
    vector<int> C(n);
    for (int i = 0; i < k; i++)
        C[n - 1 - i] = B[i][1];
    for (int i = R; i < n; i++)
        C[n - 1 - i + R - k] = B[i][1];
    for (int i = k; i < R; i++)
        C[n - 1 - i - n + R] = B[i][1];
    return C;
}




















#ifdef LOCAL

extern vector<int> solve(vector<int> A);
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t ;
    for (int test=1; test<=t; test++) {
        int n;
        cin >> n ;
        vector <int> a(n);
        for (int i=0; i<n; i++) {
            cin >> a[i] ;
        }

        for (auto ind : solve(a)) {
            cout << ind << " ";
        }
        cout << endl ;
    }
    cout << endl ;
    return 0;
}

#endif // LOCAL
