First, set all numbers to one. Increase if necessary.

t = int(input())

while t > 0:
    t -= 1
    n, k = map(int, input().split())
    triplets = [[] for i in range(n + 1)]
    while k > 0:
        k -= 1
        l, r, m = map(int, input().split())
        triplets[m].append((l - 1, r))  # [l, r)
    a = [1] * n
    for i in range(1, n + 1):
        for rng in triplets[i]:
            if min(a[rng[0]:rng[1]]) == i:
                a[rng[0]:rng[1]] = [i + 1] * (rng[1] - rng[0])
    if n + 1 in a:
        print(-1)
    else:
        print(*a)

Don't pick numbers that if you pick them, AND will not become k for sure. Pick everything else.

t = int(input())

while t > 0:
    t -= 1
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    ans = []
    cur = (1 << 30) - 1
    for i in range(n):
        if a[i] & k == k:
            ans.append(i + 1)
            cur &= a[i]
    if cur == k:
        print('YES', '\n', len(ans), '\n', *ans)
    else:
        print('NO')

Backtrack and dp both work.

// In the name of Allah.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N = 3000;

int n, a[MAX_N], b[MAX_N];
map<array<int, 2>, int> cache[MAX_N];
int solve(int i = 0, int mx = INT_MIN, int level = INT_MIN) {
    if (i == n)
        return 0;
    if (cache[i].contains({mx, level}))
        return cache[i][{mx, level}];
    if (b[i] <= level || a[i] > level)
        return cache[i][{mx, level}] = solve(i + 1, max(mx, b[i]), max(level, mx + b[i])) + (b[i] <= level);
    return cache[i][{mx, level}] = max(solve(i + 1, max(mx, a[i]), max(level, mx + a[i])) + 1,
        solve(i + 1, max(mx, b[i]), max(level, mx + b[i])));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            cache[i].clear();
        }
        for (int i = 0; i < n; ++i) {
            cin >> b[i];
            if (a[i] > b[i])
                swap(a[i], b[i]);
        }
        cout << solve() << '\n';
    }
}

Use some primes, and also 6.

MAX_N = 2000000
is_p = [True] * MAX_N
for i in range(2, MAX_N):
    if not is_p[i]:
        continue
    for j in range(i * i, MAX_N, i):
        is_p[j] = False

prs = [i for i in range(2, MAX_N) if is_p[i]]

t = int(input())

while t > 0:
    t -= 1
    n, k = map(int, input().split())
    if k > n * (n - 1) / 2:
        print(-1)
        continue
    ptr = len(prs) - 1
    while n or k:
        if k >= n - 1:
            print(prs[ptr], end=' ')
            ptr -= 1
            k -= n - 1
            n -= 1
        else:
            if ptr > 0:
                ptr = 1
                print(6, end=' ')
            else:
                print(2, end=' ')
            n -= 1
    print()

DSU, but hard!

// In the name of Allah.

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200000;

int p[MAX_N], val[MAX_N], k[MAX_N], rev[MAX_N];
// if p[i] == -1: a[i] = val[i]
// o.w. a[i] = k[i] + rev[i] * a[p[i]]

int root(int v) {
    if (p[v] == -1)
        return v;
    int r = root(p[v]);
    if (r == p[v])
        return r;
    // a[v] = k[v] + rev[v] * a[p[v]]
    // a[p[v]] = k[p[v]] + rev[p[v]] * a[r]
    // => a[v] = k[v] + rev[v] * k[p[v]] + rev[v] * rev[p[v]] * a[r]

    // a[v] = k'[v] + rev'[v] * a[r]
    k[v] += rev[v] * k[p[v]];
    rev[v] *= rev[p[v]];
    return p[v] = r;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    fill(p, p + n, -1);
    fill(val, val + n, -1);
    fill(rev, rev + n, 1);
    while (q--) {
        int t, i, j, qk;
        cin >> t >> i >> j;
        --i;
        --j;
        if (t == 1) {
            cin >> qk;
            // a[i] + a[j] = qk
            int ri = root(i), rj = root(j);
            // cerr << ri << ' ' << rj << '\n';
            if (ri == rj) {
                // cerr << "r: " << rev[i] << ' ' << rev[j] << '\n';
                if (val[ri] != -1 || rev[i] != rev[j])
                    continue;
                // a[i] = k[i] + rev[i] * a[ri]
                // a[j] = k[j] + rev[j] * a[ri]
                // => 2 * rev[i] * a[ri] = qk - k[i] - k[j]
                // a[ri] = (qk - k[i] - k[j]) / (2 * rev[i])
                // cerr << "found!\n";
                val[ri] = (qk - k[i] - k[j]) / (2 * rev[i]);
            }
            else {
                // Make ri parent of rj
                // a[i] = k[i] + rev[i] * a[ri]
                // a[j] = k[j] + rev[j] * a[rj]
                if (val[rj] != -1) {
                    // k[i] + rev[i] * a[ri] + k[j] + rev[j] * a[rj] = qk
                    val[ri] = (qk - (k[i] + k[j] + rev[j] * val[rj])) * rev[i];
                    continue;
                }
                // a[rj] = k[rj] + rev[rj] * a[ri]
                // a[rj] = (qk - (k[i] + rev[i] * a[ri] + k[j])) * rev[j]
                // a[rj] = rev[j] * (qk - k[i] - k[j]) - rev[i] * rev[j] * a[ri]
                k[rj] = rev[j] * (qk - k[i] - k[j]);
                rev[rj] = -rev[i] * rev[j];
                p[rj] = ri;
            }
        }
        else {
            int ri = root(i), rj = root(j);
            if (val[ri] != -1 && val[rj] != -1)
                cout << k[i] + rev[i] * val[ri] + k[j] + rev[j] * val[rj] << '\n';
            else if (ri == rj && rev[i] != rev[j]) {
                // a[i] = k[i] + rev[i] * a[ri]
                // a[j] = k[j] + rev[j] * a[ri]
                cout << k[i] + k[j] << '\n';
            }
            else
                cout << "-1\n";
        }
    }
}