思路

由于所有数之和是 $4$ 的倍数，我们可以把房间分成若干"和为 $4$ 的倍数"的安全块，再按顺序拼接起来。先把所有房间按 $a_i\bmod 4$ 分成四类：余 $0$、余 $1$、余 $2$、余 $3$。余 $0$ 的房间放在任意位置都安全（不会改变当前模 $4$ 值），因此可以先全部输出。

除余 $0$ 外，其他房间需要按若干安全块排列，使得每个块内部的前缀和模 $4$ 都不是 $1$，且整块和 $\equiv 0\pmod 4$。可安全使用的块及其输出顺序（按使中间模值不为 $1$ 的顺序）为：

• $(3,1)$：先输出余 $3$，再输出余 $1$；累加模值序列 $3\to0$。
• $(2,2)$：两个余 $2$；序列 $2\to0$。
• $(3,3,2)$：两个余 $3$ 再一个余 $2$；序列 $3\to2\to0$。
• $(2,1,1)$：一个余 $2$ 再两个余 $1$；序列 $2\to3\to0$。

为什么这四种块就够用。 任何安全块的累加过程从 $0$ 出发，第一步不能是余 $1$（否则会到 $1$），所以第一次到达的状态只能是 $2$ 或 $3$；此后每一步只能在 $2,3$ 之间转移：状态 $2$ 只能接余 $1$（到 $3$）或余 $2$（到 $0$ 结束），状态 $3$ 只能接余 $3$（到 $2$）或余 $1$（到 $0$ 结束）。把所有以 $0$ 结尾的安全块按上述结构写出来，其各类计数只能是

$$(t,2,t),\quad(t+2,1,t),\quad(t+1,0,t+1),\quad(t,1,t+2)\quad(t\ge0),$$

而它们分别等于 $(2,2)+t\cdot(3,1)$、$(2,1,1)+t\cdot(3,1)$、$(t+1)\cdot(3,1)$、$(3,3,2)+t\cdot(3,1)$（按（余1,余2,余3）的计数记）。也就是说，每个安全块都能拆成上面四种块的组合，四种块足以覆盖所有有解情况。

于是问题变为：能否用上述若干块恰好耗尽各类元素计数。代码用 c0..c3 记录各类数量，先输出所有余 $0$ 的房间，然后枚举四种块的所有排列顺序（共 $4!=24$ 种）：每遇到一种块就尽可能多地构造，并从对应计数中减去消耗，最后检查余 $1$、余 $2$、余 $3$ 是否全部消耗完。若存在某种顺序能够耗尽，就按该顺序输出各房间的原始下标；否则输出 $-1$。

注意余 $0$ 必须全部输出在最前面，之后各块只由余 $1,2,3$ 组成，块与块拼接处模值都回到 $0$，因此整体仍然安全。

复杂度：分组 $O(n)$；枚举 $4!$ 种顺序，每种顺序的消耗为常数次操作，总计 $O(n)$。

代码

#include<bits/stdc++.h>
#define int long long
#define dd double
#define str string
#define el cout << '\n'
#define re return
#define ff first
#define ss second
#define pll pair<int,int>
#define pdd pair<dd,dd>
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;

const int N = 1e5+10;
vector<queue<int>>v(4);   // v[r] 存放模 4 余 r 的房间下标，按出现顺序
int n;
vector<int>cnt;           // cnt[r] 为模 4 余 r 的房间数量
int a[N];

// 消耗 (3,1) 块：余 3 与余 1 各取 mi 个，尽量多做
void dec(int& a1, int& a2){
    int mi = min(a1, a2);
    a1 -= mi;
    a2 -= mi;
}

// 消耗 (3,3,2) 或 (2,1,1) 块：按 a1 每两个配 a2 一个，尽量多做
void dec2(int& a1, int& a2){
    int mi = min(a1/2, a2);
    a1 -= mi*2;
    a2 -= mi;
}

// 四种块的编号：
// 1：(3,1) 块；2：(3,3,2) 块；3：(2,2) 块；4：(2,1,1) 块
// 按 arr 给出的顺序检测能否把余 1,2,3 全部耗尽
bool check(vector<int>arr, vector<int>c){
    for(int i=0;i<4;i++){

        if(arr[i]==1){// 处理 (3,1) 块
            dec(c[3], c[1]);
        }else if(arr[i]==2){// 处理 (3,3,2) 块
            dec2(c[3], c[2]);
        }else if(arr[i]==3){// 处理 (2,2) 块
            c[2]%=2;              // 两个两个地消耗余 2
        }else if(arr[i]==4){// 处理 (2,1,1) 块
            dec2(c[1], c[2]);
        }
    }
    // 三个非零余数都清空才说明该顺序可行
    if(c[1]==0 and c[2]==0 and c[3]==0){
        return 1;
    }else{
        return 0;
    }
}

// 按该处理顺序真正输出答案
void pr(vector<int>arr, vector<int>c){

    while (v[0].size())// 先输出所有余 0 的房间，它们不影响安全性
    {
        cout<<v[0].front()<<' ';
        v[0].pop();
    }

    for(int i=0;i<4;i++){

        if(arr[i]==1){// 处理 (3,1) 块
            int mi =min(c[3], c[1]);
            c[3] -= mi;
            c[1] -= mi;
            while (mi-->0)
            {
                int x = v[3].front();v[3].pop();
                int y = v[1].front();v[1].pop();
                cout<<x<<' '<<y<<' ';       // 先余 3 再余 1
            }
        }else if(arr[i]==2){// 处理 (3,3,2) 块
            int mi =min(c[3]/2, c[2]);
            c[3] -= mi*2;
            c[2] -= mi;
            while (mi-->0)
            {
                int x = v[3].front();v[3].pop();
                int y = v[3].front();v[3].pop();
                int z = v[2].front();v[2].pop();
                cout<<x<<' '<<y<<' '<<z<<' ';
            }
        }else if(arr[i]==3){// 处理 (2,2) 块
            int mi = c[2]/2;
            c[2] -= mi*2;
            while (mi-->0)
            {
                int x = v[2].front();v[2].pop();
                int y = v[2].front();v[2].pop();
                cout<<x<<' '<<y<<' ';
            }
        }else if(arr[i]==4){// 处理 (2,1,1) 块
            int mi =min(c[1]/2, c[2]);
            c[1] -= mi*2;
            c[2] -= mi;
            while (mi-->0)
            {
                int x = v[2].front();v[2].pop();
                int y = v[1].front();v[1].pop();
                int z = v[1].front();v[1].pop();
                cout<<x<<' '<<y<<' '<<z<<' ';
            }
        }
    }
    cout<<endl;
}

void go(){
    cnt = {0,0,0,0};
    v ={{}, {}, {}, {}};// 多组数据，必须先重置全局结构

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        v[a[i]%4].push(i);   // 记录原始下标，按余数分类
        cnt[a[i]%4]++;
    }

    vector<int>type = {1,2,3,4};   // 从四种块的一个初始排列开始枚举
    int times = 25;                // 4! = 24 种排列，多跑一次保证遍历完整
    while (times--)
    {
        if(check(type, cnt)){      // 该处理顺序可行
            pr(type, cnt);
            re;
        }

        next_permutation(all(type));
    }

    cout<<-1<<endl;   // 所有顺序都不行，说明无解
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int _=1;
    cin >>_;          // 本题有多组测试数据
    while(_--){
        go();
    }
    return 0;
}