#include <bits/stdc++.h>
using namespace std;
template <typename S, typename T>
ostream& operator<<(ostream& out, pair<S, T> const& p) {
  out << '(' << p.first << ", " << p.second << ')';
  return out;
}
template <typename T>
ostream& operator<<(ostream& out, vector<T> const& v) {
  long long l = v.size();
  for (long long i = 0; i < l - 1; i++) out << v[i] << ' ';
  if (l > 0) out << v[l - 1];
  return out;
}
template <typename T>
void trace(const char* name, T&& arg1) {
  cout << name << " : " << arg1 << "\n";
}
template <typename T, typename... Args>
void trace(const char* names, T&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  trace(comma + 1, args...);
}
bitset<7002> singleton[7002];
bitset<7002> mobius_inv[7002];
bitset<7002> arr[100003];
bitset<7002> mobius;
int n, q;
int i, j, k;
void calc_mobius() {
  mobius.set();
  for (i = 2; i < 7002; i++) {
    for (j = i * i; j < 7002; j += i * i) {
      mobius[j] = 0;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> q;
  for (i = 1; i < 7002; i++) {
    for (j = 1; j * j <= i; j++) {
      if (i % j == 0) {
        singleton[i][j] = 1;
        singleton[i][i / j] = 1;
      }
    }
  }
  calc_mobius();
  for (k = 1; k < 7002; k++) {
    for (j = k; j < 7002; j += k) {
      mobius_inv[k][j] = mobius[j / k];
    }
  }
  int type, x, y, z, v;
  int i;
  for (i = 0; i < q; i++) {
    cin >> type;
    if (type == 1) {
      cin >> x >> v;
      arr[x] = singleton[v];
    } else if (type == 2) {
      cin >> x >> y >> z;
      arr[x] = arr[y] ^ arr[z];
    } else if (type == 3) {
      cin >> x >> y >> z;
      arr[x] = arr[y] & arr[z];
    } else {
      cin >> x >> v;
      cout << ((arr[x] & mobius_inv[v]).count() % 2);
    }
  }
  cout << "\n";
}
