#include <bits/stdc++.h>
using std::cerr;
using std::endl;
const int N = 1e5 + 5, M = 7001;
int n, q, mu[N], vis[N], pr[N], tot;
std::bitset<M> bit[N], query[M], pre[M];
std::vector<int> fac[N];
int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);
  std::cin >> n >> q;
  mu[1] = 1;
  for (int i = 2; i < M; ++i) {
    if (!vis[i]) pr[++tot] = i, mu[i] = -1, fac[i].push_back(i);
    for (int j = 1; j <= tot && i * pr[j] < M; ++j) {
      vis[i * pr[j]] = 1;
      fac[i * pr[j]] = fac[i];
      if (!(i % pr[j])) break;
      mu[i * pr[j]] = -mu[i];
      fac[i * pr[j]].push_back(pr[j]);
    }
  }
  for (int i = 1; i < M; ++i) fac[i].push_back(i);
  for (int i = 1; i < M; ++i) {
    for (int j = i; j < M; j += i) {
      if (mu[j / i]) query[i][j] = 1;
      pre[j][i] = 1;
    }
  }
  while (q--) {
    int o, x, y, z;
    std::cin >> o >> x >> y;
    if (o == 1) {
      bit[x] = pre[y];
    } else if (o == 2) {
      std::cin >> z;
      bit[x] = bit[y] ^ bit[z];
    } else if (o == 3) {
      std::cin >> z;
      bit[x] = bit[y] & bit[z];
    } else {
      int ans = (bit[x] & query[y]).count();
      ans &= 1;
      std::cout << ans;
    }
  }
  std::cout << '\n';
  return 0;
}
