#include <bits/stdc++.h>
using namespace std;
inline int gi() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + ch - 48;
    ch = getchar();
  }
  return x * f;
}
template <typename T>
inline bool Max(T &a, T b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
inline bool Min(T &a, T b) {
  return a > b ? a = b, 1 : 0;
}
const int N = 1e5 + 7, Num = 7000;
int n;
bitset<Num> Mu[N], g[N], a[N], t;
int mu[N], pri[N], icn[N], pc, q;
void sieve(int n) {
  int to;
  mu[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (!icn[i]) {
      pri[++pc] = i, mu[i] = -1;
    }
    for (int j = 1; j <= pc && (to = i * pri[j]) <= n; ++j) {
      icn[to] = 1;
      if (i % pri[j] == 0) {
        mu[to] = 0;
        break;
      }
      mu[to] = -mu[i];
    }
  }
}
int main() {
  n = gi(), q = gi();
  sieve(Num);
  for (int i = 1; i <= Num; ++i) {
    for (int j = i; j <= Num; j += i) {
      Mu[i][j] = abs(mu[j / i]);
    }
  }
  for (int i = 1; i <= Num; ++i) {
    for (int j = 1, l = (int)sqrt(i); j <= l; ++j)
      if (i % j == 0) {
        a[i][j] = 1;
        if (j * j != i) a[i][i / j] = 1;
      }
  }
  int x, y, z, opt, v;
  while (q--) {
    opt = gi(), x = gi();
    if (opt == 1) {
      v = gi();
      g[x] = a[v];
    }
    if (opt == 2) {
      y = gi(), z = gi();
      g[x] = g[y] ^ g[z];
    }
    if (opt == 3) {
      y = gi(), z = gi();
      g[x] = g[y] & g[z];
    }
    if (opt == 4) {
      v = gi();
      t = Mu[v] & g[x];
      printf("%d", t.count() & 1);
    }
  }
  return 0;
}
