#include <bits/stdc++.h>
std::bitset<7020> b[101000], d[101000], f[101000], bt;
int n, q, op, x, y, z, v, ans, pri[7020], pt, mu[7020], te;
bool isp[7020];
int main() {
  mu[1] = 1;
  for (int i = 2; i <= 7000; i++) {
    if (!isp[i]) {
      pri[++pt] = i;
      mu[i] = -1;
    }
    for (int j = 1; j <= pt; j++) {
      te = i * pri[j];
      if (te > 7000) break;
      isp[te] = 1;
      if (i % pri[j] == 0) break;
      mu[te] = -mu[i];
    }
  }
  for (int i = 1; i <= 7000; i++)
    for (int j = i; j <= 7000; j += i) d[j][i] = 1;
  for (int v = 1; v <= 7000; v++)
    for (int i = v; i <= 7000; i += v)
      if (mu[i / v]) f[v][i] = 1;
  scanf("%d%d", &n, &q);
  while (q--) {
    scanf("%d", &op);
    if (op == 1) {
      scanf("%d%d", &x, &v);
      b[x] = d[v];
    }
    if (op == 2) {
      scanf("%d%d%d", &x, &y, &z);
      b[x] = b[y] ^ b[z];
    }
    if (op == 3) {
      scanf("%d%d%d", &x, &y, &z);
      b[x] = b[y] & b[z];
    }
    if (op == 4) {
      scanf("%d%d", &x, &v);
      bt = b[x] & f[v];
      ans = bt.count() & 1;
      putchar('0' + ans);
    }
  }
  return 0;
}
