#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 100100;
const long long INF = 2000000100;
const long long MOD = 998244353;
const long long MAXV = 7010;
int N, Q;
bitset<MAXV> st[MAXN], pre1[MAXV], pre4[MAXV];
void make1() {
  for (int v = 1; v <= MAXV; v++) {
    for (int i = 1; i <= v; i++) {
      if (v % i == 0) pre1[v][i] = 1;
    }
  }
}
void make4() {
  vector<int> f;
  for (int v = 1; v <= MAXV; v++) {
    bool ok = true;
    for (int i = 2;; i++) {
      if (i * i > v) break;
      if (v % (i * i) == 0) ok = false;
    }
    if (ok) f.push_back(v);
  }
  for (int v = 1; v <= MAXV; v++) {
    for (int i = 0; i < (int)f.size(); i++) {
      if (v * f[i] > MAXV) break;
      pre4[v][v * f[i]] = true;
    }
  }
}
void output(bitset<MAXV> b) {
  for (int i = 1; i <= 30; i++) {
    cerr << b[i];
  }
  cerr << "\n";
}
void debug() {
  for (int i = 1; i <= 10; i++) {
    output(pre1[i]);
  }
  cerr << "\n";
}
int main() {
  scanf("%d %d", &N, &Q);
  make1();
  make4();
  int t;
  int x, y, z, v;
  for (int q = 0; q < Q; q++) {
    scanf("%d", &t);
    if (t == 1) {
      scanf("%d %d", &x, &v);
      st[x] = pre1[v];
    } else if (t == 2) {
      scanf("%d %d %d", &x, &y, &z);
      st[x] = st[y] ^ st[z];
    } else if (t == 3) {
      scanf("%d %d %d", &x, &y, &z);
      st[x] = st[y] & st[z];
    } else {
      scanf("%d %d", &x, &v);
      printf("%d", ((st[x] & pre4[v]).count()) % 2);
    }
  }
  cout << "\n";
}
