#include <bits/stdc++.h>
using namespace std;
inline int read() {
  register int x = 0, f = 1;
  register char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
  return x * f;
}
int n, m, prim[7001], vis[7001], mu[7001], cnt;
bitset<7001> G[7001], a[100005], u[7001];
int main() {
  n = read(), m = read(), mu[1] = 1;
  for (register int i = 2; i <= 7000; ++i) {
    if (!vis[i]) prim[++cnt] = i, mu[i] = -1;
    for (register int j = 1; j <= cnt && prim[j] * i <= 7000; ++j) {
      vis[i * prim[j]] = 1;
      if (i % prim[j] == 0) break;
      mu[i * prim[j]] = -mu[i];
    }
  }
  for (register int i = 1; i <= 7000; ++i) {
    for (register int j = i; j <= 7000; j += i)
      G[j][i] = 1, u[i][j] = mu[j / i] != 0;
  }
  while (m--) {
    int opt = read(), x = read();
    if (opt == 1) a[x] = G[read()];
    if (opt == 2) a[x] = a[read()] ^ a[read()];
    if (opt == 3) a[x] = a[read()] & a[read()];
    if (opt == 4) printf("%d", (u[read()] & a[x]).count() & 1);
  }
  return 0;
}
