#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void ckmx(T &x, T y) {
  x = max(x, y);
}
template <typename T>
inline void ckmi(T &x, T y) {
  x = min(x, y);
}
template <typename T>
void read(T &x) {
  x = 0;
  int f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
  x *= f;
}
bitset<7005> ad[7005], qy[7005], a[100005];
int p[7010], mu[7010], ss[7010], ssn;
void pre(int n) {
  for (int i = 1; i <= n; ++i) p[i] = i;
  mu[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (p[i] == i) ss[++ssn] = i, mu[i] = 1;
    for (int j = 1; j <= ssn; ++j) {
      if (i * ss[j] > n || p[i] < ss[j]) break;
      p[i * ss[j]] = ss[j];
      if (p[i] == ss[j])
        mu[i * ss[j]] = 0;
      else
        mu[i * ss[j]] = mu[i];
    }
  }
}
int main() {
  pre(7000);
  for (int i = 1; i <= 7000; ++i)
    for (int j = 1; i * j <= 7000; ++j) ad[i * j][i] = 1, qy[i][i * j] = mu[j];
  int n, q;
  read(n);
  read(q);
  while (q--) {
    int op, x, y, z;
    read(op);
    read(x);
    read(y);
    if (op == 1)
      a[x] = ad[y];
    else if (op == 2)
      read(z), a[x] = a[y] ^ a[z];
    else if (op == 3)
      read(z), a[x] = a[y] & a[z];
    else {
      bitset<7005> ans = a[x] & qy[y];
      putchar('0' + (ans.count() & 1));
    }
  }
  return 0;
}
