#include <bits/stdc++.h>
using namespace std;
namespace FGF {
const int N = 1e5 + 5, M = 7005;
bitset<M> f[M], g[M], a[N];
int mu[N], vis[N], p[N], cnt, n, m;
void init() {
  mu[1] = 1;
  for (int i = 2; i <= M - 5; i++) {
    if (!vis[i]) p[++cnt] = i, mu[i] = 1;
    for (int j = 1; j <= cnt && p[j] * i <= M - 5; j++) {
      vis[p[j] * i] = 1;
      if (i % p[j] == 0) break;
      mu[i * p[j]] = mu[i];
    }
  }
  for (int i = 1; i <= M - 5; i++)
    for (int j = i; j <= M - 5; j += i) f[j][i] = 1, g[i][j] = mu[j / i];
}
void work() {
  scanf("%d%d", &n, &m);
  init();
  while (m--) {
    int x, y, z, op;
    scanf("%d%d%d", &op, &x, &y);
    if (op == 1) a[x] = f[y];
    if (op == 2) scanf("%d", &z), a[x] = a[y] ^ a[z];
    if (op == 3) scanf("%d", &z), a[x] = a[y] & a[z];
    if (op == 4) printf("%d", (int)(g[y] & a[x]).count() % 2);
  }
}
}  // namespace FGF
int main() {
  FGF::work();
  return 0;
}
