#include <bits/stdc++.h>
using namespace std;
namespace Base {
const int inf = 0x3f3f3f3f, INF = 0x7fffffff;
const long long infll = 0x3f3f3f3f3f3f3f3fll, INFll = 0x7fffffffffffffffll;
template <typename T>
void read(T &x) {
  x = 0;
  int fh = 1;
  double num = 1.0;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') fh = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  if (ch == '.') {
    ch = getchar();
    while (isdigit(ch)) {
      num /= 10;
      x = x + num * (ch - '0');
      ch = getchar();
    }
  }
  x = x * fh;
}
template <typename T>
void chmax(T &x, T y) {
  x = x < y ? y : x;
}
template <typename T>
void chmin(T &x, T y) {
  x = x > y ? y : x;
}
}  // namespace Base
using namespace Base;
const int N = 100010, K = 7000;
bitset<K + 1> mp[N], g[K + 1], f[K + 1];
int n, q, use[K + 1];
int main() {
  read(n);
  read(q);
  for (int i = 2; i <= K; i++)
    if (!use[i]) {
      for (int j = i + i; j <= K; j += i) use[j] = true;
    }
  for (int i = 1; i <= K; i++) {
    use[i] = false;
    for (int j = 2; j * j <= i; j++)
      if (i % (j * j) == 0) use[i] = true;
  }
  for (int i = 1; i <= K; i++)
    for (int j = 1; j <= i; j++)
      if (i % j == 0) g[i].set(j);
  for (int i = 1; i <= K; i++)
    for (int j = i; j <= K; j++)
      if (j % i == 0 && use[j / i] == false) f[i].set(j);
  for (int i = 1; i <= q; i++) {
    int op;
    read(op);
    if (op == 1) {
      int x, y;
      read(x);
      read(y);
      mp[x] = g[y];
    }
    if (op == 2) {
      int x, y, z;
      read(x);
      read(y);
      read(z);
      mp[x] = mp[y] ^ mp[z];
    }
    if (op == 3) {
      int x, y, z;
      read(x);
      read(y);
      read(z);
      mp[x] = mp[y] & mp[z];
    }
    if (op == 4) {
      int x, y, tmp;
      read(x);
      read(y);
      tmp = (mp[x] & f[y]).count();
      printf("%d", tmp % 2);
    }
  }
  printf("\n");
  return 0;
}
