剪贴板 - dyqb13pt

#include <algorithm>
#include <cmath>
#include <iostream>
#include <ostream>
#include <random>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;

using ll = long long;
using ull = unsigned long long;

vector<pair<ll, ll>> vec;
unordered_map<ll, ll> umap;

const ll N = 2e5 + 5;

ll gcd(ll a, ll b) { return __gcd(a, b); }

ll cnt_gcd[N];
vector<ll> pf[N];
bool used[N];

void cal() {
    for (ll i = 0; i < (ll)vec.size(); i++) {
        auto x = vec[i].first;
        auto cp = x;
        for (ll j = 2; j <= sqrt(x); j++) {
            if (cp % j == 0) {
                pf[i].push_back(j);
                while (cp % j == 0) {
                    cp /= j;
                }
            }
        }
        if (cp != 1) {
            pf[i].push_back(cp);
        }
        vector<ll> prod_vec;
        for (ll stat = 0; stat < (1 << (ll)pf[i].size()); stat++) {
            ll sum = 1;
            for (ll j = 0; j < (ll)pf[i].size(); j++) {
                if ((stat >> j) & 1) {
                    sum *= pf[i][j];
                }
            }
            prod_vec.push_back(sum);
        }
        for (auto prod_x : prod_vec) {
            umap[prod_x]++;
        }
    }
    for (ll i = 0; i < (ll)vec.size(); i++) {
        for (ll stat = 0; stat < (1 << (ll)pf[i].size()); stat++) {
            ll sum = 1, bit = 0;
            for (ll j = 0; j < (ll)pf[i].size(); j++) {
                if ((stat >> j) & 1) {
                    bit++;
                    sum *= pf[i][j];
                }
            }
            cnt_gcd[i] += ((bit & 1) ? -1 : 1) * umap[sum]; // 容斥。
        }
    }
    return;
}

void solve() {
    ll n, m;
    cin >> n >> m;
    vec.clear();
    fill(used, used + n + 1, false);
    fill(cnt_gcd, cnt_gcd + n + 1, 0);
    fill(pf, pf + n + 1, vector<ll>());
    for (ll i = 0; i < n; i++) {
        ll x;
        cin >> x;
        vec.push_back(make_pair(x, i + 1));
    }
    umap.clear();
    shuffle(vec.begin(), vec.end(), mt19937(random_device()()));
    cal();
    vector<ll> ans;
    for (ll i = 0; i < 2; i++) {
        set<pair<ll, ll>> pq;
        for (ll i = 0; i < n; i++) {
            if (cnt_gcd[i] != 0 && !used[i])
                pq.insert(make_pair(cnt_gcd[i], i));
        }
        if (pq.empty()) {
            break;
        }
        auto f = *pq.begin();
        pq.erase(pq.begin());
        ll minn = 0x3f3f3f3f3f3f3f3f, mini = -1;
        used[f.second] = true;
        for (ll j = 0; j < n; j++) {
            if (gcd(vec[j].first, vec[f.second].first) == 1 &&
                cnt_gcd[j] < minn && !used[j]) {
                minn = cnt_gcd[j];
                mini = j;
            }
        }
        if (mini == -1) {
            break;
        }
        used[mini] = true;
        pq.erase(make_pair(minn, mini));
        ans.push_back(vec[f.second].second);
        ans.push_back(vec[mini].second);
        for (ll j = 0; j < n; j++) {
            if (gcd(vec[f.second].first, vec[j].first) == 1) {
                cnt_gcd[j]--;
            }
            if (gcd(vec[mini].first, vec[j].first) == 1) {
                cnt_gcd[j]--;
            }
        }
    }
    if ((ll)ans.size() < 4) {
        cout << "0\n";
        return;
    }
    for (ll i = 0; i < 4; i++) {
        cout << ans[i] << " ";
    }
    cout << "\n";
    return;
}

int main() {
    ll t;
    cin >> t;
    while (t--) {
        solve();
    }
    cout << flush;
    return 0;
}