#include <bits/stdc++.h>
using namespace std;
const int W = 7000;
inline int read() {
  int neg = 1, num = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') neg = -1;
  for (; isdigit(c); c = getchar()) num = (num << 1) + (num << 3) + c - '0';
  return neg * num;
}
int n, q, tot, pri[100010];
bool vis[100010];
bitset<7100> res, f[100010], g[W + 1000], h[W + 1000], mu;
inline void sieve() {
  vis[1] = 1;
  mu.reset();
  mu.set(1);
  for (int i = 2; i <= W; i++) {
    if (!vis[i]) pri[++tot] = i, mu.set(i);
    for (int j = 1; j <= tot && pri[j] * i <= W; j++) {
      vis[i * pri[j]] = 1;
      if (i % pri[j] == 0) break;
      if (mu[i]) mu.set(i * pri[j]);
    }
  }
}
signed main() {
  n = read();
  q = read();
  sieve();
  for (int i = 1; i <= W; i++)
    for (int j = i; j <= W; j += i) {
      g[j].set(i);
      if (mu[j / i]) h[i].set(j);
    }
  for (int i = 1; i <= q; i++) {
    int opt = read(), x = read(), y = read(), z;
    if (opt == 1)
      f[x].reset(), f[x] = g[y];
    else if (opt == 2)
      z = read(), f[x] = f[y] ^ f[z];
    else if (opt == 3)
      z = read(), f[x] = f[y] & f[z];
    else if (opt == 4)
      res = h[y] & f[x], putchar((res.count() & 1) + '0');
  }
  return 0;
}
