#include <bits/stdc++.h>
using namespace std;
long long n, q, op, t1, t2, t3;
bitset<7005> k[7005], f[100005], g[7005], m[7005];
long long pr[7005], cnt = 0, mu[7005];
bool vis[7005];
inline void xxs() {
  mu[1] = 1;
  for (int i = 2; i < 7005; i++) {
    if (!vis[i]) pr[++cnt] = i, mu[i] = -1;
    for (int j = 1; j <= cnt && i * pr[j] < 7005; j++) {
      long long t = i * pr[j];
      vis[t] = 1;
      if (i % pr[j] == 0) break;
      mu[t] = -mu[i];
    }
  }
  for (int i = 1; i < 7005; i++) {
    for (int j = i; j < 7005; j += i) {
      k[j][i] = 1;
      if (mu[j / i] != 0) m[i][j] = 1;
    }
  }
}
inline long long read() {
  long long f = 0, s = 0;
  char c = getchar();
  while (c > '9' || c < '0') f = (c == '-'), c = getchar();
  while (c >= '0' && c <= '9')
    s = (s << 3) + (s << 1) + (c ^ '0'), c = getchar();
  return f ? -s : s;
}
int main() {
  n = read();
  q = read();
  xxs();
  for (int i = 1; i <= q; i++) {
    op = read();
    if (op == 1) {
      t1 = read();
      t2 = read();
      f[t1] = k[t2];
    } else if (op == 2) {
      t1 = read();
      t2 = read();
      t3 = read();
      f[t1] = f[t2] ^ f[t3];
    } else if (op == 3) {
      t1 = read();
      t2 = read();
      t3 = read();
      f[t1] = f[t2] & f[t3];
    } else if (op == 4) {
      t1 = read();
      t2 = read();
      printf("%lld", (m[t2] & f[t1]).count() % 2);
    }
  }
  return 0;
}
