#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int tot;
int f[N], mu[N], pr[N];
bitset<7005> a[N], G[N], Mu[N];
template <typename T>
inline void chkmax(T &x, T y) {
  x = max(x, y);
}
template <typename T>
inline void chkmin(T &x, T y) {
  x = min(x, y);
}
template <typename T>
inline void read(T &x) {
  T f = 1;
  x = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -f;
  for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
  x *= f;
}
inline void prework() {
  mu[1] = f[1] = 1;
  for (int i = 2; i <= 7000; ++i) {
    if (!f[i]) {
      f[i] = i;
      mu[i] = -1;
      pr[++tot] = i;
    }
    for (int j = 1; j <= tot && i * pr[j] <= 7000; ++j) {
      f[i * pr[j]] = pr[j];
      if (pr[j] == f[i]) break;
      mu[i * pr[j]] = -mu[i];
    }
  }
  return;
}
int main() {
  prework();
  for (int i = 1; i <= 7000; ++i)
    for (int j = i; j <= 7000; j += i) G[j][i] = 1, Mu[i][j] = mu[j / i] != 0;
  int n, q;
  read(n), read(q);
  while (q--) {
    int op, x, y;
    read(op), read(x), read(y);
    if (op == 1)
      a[x] = G[y];
    else if (op == 2) {
      int z;
      read(z);
      a[x] = a[y] ^ a[z];
    } else if (op == 3) {
      int z;
      read(z);
      a[x] = a[y] & a[z];
    } else
      printf("%d", ((a[x] & Mu[y]).count() & 1));
  }
  printf("\n");
  return 0;
}
