JSCPC2025B.cpp

#include <bits/stdc++.h>
using namespace std;

using PII = pair<int, int>;
using Mat = vector<bitset<40>>;

struct Basis {
    int b[30];

    bool ins(int x) {
        for (int i = 29; i >= 0; i--) {
            if (x >> i & 1) {
                if (!b[i]) {
                    b[i] = x;
                    return true;
                }
                x ^= b[i];
            }
        }
        return false;
    }

    void clear() {
        memset(b, 0, sizeof b);
    }
} B;


// n: rows
// m: columns, 0 for constant
tuple<bool, vector<int>> gauss(Mat& mat, int n, int m) {
    int row = 1;
    vector<int> pivot(n+1);
    for (int p = 1; p <= m; p++) {
        int cur = row;
        while (cur <= n && !mat[cur].test(p)) cur++;
        if (cur > n) continue;
        pivot[row] = p;
        if (cur != row) swap(mat[row], mat[cur]);
        for (int i = 1; i <= n; i++) {
            if (i != row && mat[i].test(p)) {
                mat[i] ^= mat[row];
            }
        }
        row++;
    }

    vector<int> sol(m+1);
    for (int i = 1; i <= n; i++) {
        if (!pivot[i] && mat[i][0]) return {false, {}};
        sol[pivot[i]] = mat[i][0];
    }
    return {true, sol};
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, x;
    cin >> n >> x;
    vector<int> a(n+1);

    vector<int> vals;


    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (B.ins(a[i])) {
            vals.push_back(a[i]);
        }
    }

    // Special case
    if (x == 0) {
        cout << "1\n";
        cout << "1 " << a[1] << ' ' << a[1] << '\n';
        return 0;
    }

    vector<int> andvals;
    vector<tuple<int, int, int>> steps;
    do {
        for (int av: andvals) vals.push_back(av);
        andvals.clear();
        for (int i = 0; i < vals.size(); i++) {
            for (int j = i+1; j < vals.size(); j++) {
                if (B.ins(vals[i] & vals[j])) {
                    steps.push_back({2, vals[i], vals[j]});
                    andvals.push_back(vals[i] & vals[j]);
                }
            }
        }
    } while (andvals.size() != 0);

    int vars = vals.size();
    int eqs = 30;

    Mat mat(31);
    for (int j = 1; j <= 30; j++) {
        mat[j][0] = x >> (j - 1) & 1;
    }

    for (int i = 0; i < vals.size(); i++) {
        for (int j = 1; j <= 30; j++) {
            mat[j][i + 1] = vals[i] >> (j - 1) & 1;
        }
    }

    auto [has, sol] = gauss(mat, eqs, vars);
    if (!has) {
        cout << "-1\n";
        return 0;
    }

    int now = 0;
    for (int i = 0; i < vals.size(); i++) {
        if (!sol[i+1]) continue;
        if (now != 0) {
            steps.push_back({1, now, vals[i]});
        }
        now ^= vals[i];
    }

    cout << steps.size() << '\n';
    for (auto [t, a, b] : steps) {
        cout << t << ' ' << a << ' ' << b << '\n';
    }

    return 0;
}