#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 1;
const int P = 7000 + 1;
const int M = 7150;
bitset<M> a[N];
vector<int> v[P];
int val[P];
bitset<M> mu[P];
int m[P];
int pr[P];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  for (int i = 1; i < P; i++) {
    for (int j = i; j < P; j += i) {
      v[j].push_back(i);
    }
    m[i] = 1;
  }
  for (int i = 2; i < P; i++) {
    if (!pr[i]) {
      for (int j = i; j < P; j += i) {
        if (j % (i * i) == 0) m[j] = 0;
      }
    }
  }
  for (int i = 1; i < P; i++) {
    val[i] = P / i;
    val[i] += val[i - 1];
  }
  for (int i = 1; i < P; i++) {
    mu[i].reset();
    for (int j = i; j < P; j += i) {
      mu[i][j] = (m[j / i] == 0 ? 0 : 1);
    }
  }
  int n, q;
  cin >> n >> q;
  while (q--) {
    int t, x, y, z, vl;
    cin >> t;
    if (t == 1) {
      cin >> x >> vl;
      a[x].reset();
      for (auto it : v[vl]) {
        a[x][it] = 1;
      }
    }
    if (t == 2) {
      cin >> x >> y >> z;
      a[x] = a[y] ^ a[z];
    }
    if (t == 3) {
      cin >> x >> y >> z;
      a[x] = a[y] & a[z];
    }
    if (t == 4) {
      cin >> x >> vl;
      bitset<M> temp = a[x] & mu[vl];
      cout << ((temp.count()) & 1);
    }
  }
}
