#include <bits/stdc++.h>
std::bitset<7005> vis;
int mu[7005], p[7005], tot, n, q;
inline void init() {
  int n = 7005 - 3;
  mu[1] = 1;
  for (long long i = (2); i <= (n); ++i) {
    if (!vis[i]) p[++tot] = i, mu[i] = -1;
    vis[i] = 1;
    for (int j = 1; j <= tot && i * p[j] <= n; ++j) {
      vis[i * p[j]] = 1;
      if (!(i % p[j])) break;
      mu[i * p[j]] = -mu[i];
    }
  }
}
std::bitset<7005> s[100005], e[7005], smu[7005];
int main() {
  init();
  scanf("%d %d", &n, &q);
  int up = 7000;
  for (long long i = (1); i <= (up); ++i)
    for (int j = i, cnt = 1; j <= up; ++cnt, j += i)
      e[j][i] = 1, smu[i][j] = (mu[cnt] != 0);
  while (q--) {
    int opt, a, b, c;
    scanf("%d %d %d", &opt, &a, &b);
    if (opt == 1)
      s[a] = e[b];
    else if (opt == 2) {
      scanf("%d", &c);
      s[a] = s[b] ^ s[c];
    } else if (opt == 3) {
      scanf("%d", &c);
      s[a] = s[b] & s[c];
    } else
      printf("%d", (s[a] & smu[b]).count() & 1);
  }
  return 0;
}
