我靠，太神了。我靠，太神了。我靠，太神了。

只有一种询问，而且只查询奇偶性，联想到二进制相关；值域很小，联想到 bitset 维护。
怎么维护呢？设 $c_{S,i}$ 表示 $S$ 中元素 $i$ 出现的次数的奇偶性，用 bitset 存。
那么操作一好做，操作二好做，操作三什么 b 东西。

$\gcd$ 长得很欠揍，试图反演。
设 $f_{S,i}$ 表示集合 $S$ 中 $i$ 的倍数出现的次数奇偶性。
则有 $f_{S,i} = \sum\limits_{i ~|~ j} c_{S,j}$，反演可得 $c_{S,i} = \sum\limits_{i ~|~ j} \mu(\frac{j}{i}) f_{S,j}$。
这样会给操作带来怎样的变化？

操作 1

好做。

操作 2

直接把两个集合并在一起，就是 $f_{S,i} = f_{A,i} + f_{B,i}$，再 $\bmod 2$ 相当于是 bitset 异或运算。

操作 3

又是这个欠揍的 $\gcd$。

$$f_{S,i} = \sum\limits_{x} \sum\limits_{y} c_{A,x} \times c_{B,y} [i ~|~ \gcd(x,y) ]$$

是 $\gcd$ 的因数就相当于同时是二者的因数。

$$f_{S,i} = \sum\limits_{x} c_{A,x} [i ~|~ x] \sum\limits_{y} c_{B,y} [i ~|~ y]$$

这不就 $f$ 的定义？

$$f_{S,i} = f_{A,i} \times f_{B,i}$$

最后要 $\bmod 2$。这就相当于是与运算了。

操作 4

比较神秘。
式子再抄一遍：$c_{S,i} = \sum\limits_{i ~|~ j} \mu(\frac{j}{i}) f_{S,j}$。
由于 $|\mu(x)| \leq 1$，所以考虑记 $g_{i,j} = \mu(\frac{j}{i}) \And [i ~|~ j]$，这是好预处理的。
那么相当于求 $c_{S,i} = \sum\limits_{j} g_{i,j} \And f_{S,j}$。
那么把 $g_i$ 和 $f_S$ 与运算一下就行，答案为 $popcount$。

代码

日常不写 mu[1] = 1。

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

const int N = 1e5 + 5, M = 7005;

int n, q;
int prime[M], tot, mu[M];
bool st[M];
bitset<M> f[N], g[M], p[M];
void init() {
    mu[1] = 1;
    for (int i = 2; i <= 7000; i++) {
        if (!st[i]) prime[++tot] = i, mu[i] = -1;
        for (int j = 1; j <= tot && i * prime[j] <= 7000; j++) {
            st[i * prime[j]] = 1;
            if (i % prime[j] == 0) { mu[i * prime[j]] = 0; break; }
            mu[i * prime[j]] = /*-*/mu[i];
        }
    }
    for (int i = 1; i <= 7000; i++)
        for (int j = i; j <= 7000; j += i)
            g[i][j] = mu[j / i], p[j][i] = 1;
}

int main() {
    init();
    scanf("%d%d", &n, &q);
    while (q--) {
        int opt, x, y, z, v; scanf("%d", &opt);
        if (opt == 1) scanf("%d%d", &x, &v), f[x] = p[v];
        else if (opt == 2) scanf("%d%d%d", &x, &y, &z), f[x] = f[y] ^ f[z];
        else if (opt == 3) scanf("%d%d%d", &x, &y, &z), f[x] = f[y] & f[z];
        else scanf("%d%d", &x, &v), putchar( ( (f[x] & g[v]).count() & 1 ) ^ 48 );
    }
    return 0;
}