#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int sum = 0, f = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    sum = sum * 10 + ch - '0';
    ch = getchar();
  }
  return f * sum;
}
const int M = 7001;
const int N = 100005;
int n, m;
bitset<M> a[N], mu, Mu[M], p[M];
inline void pre() {
  mu.set();
  for (int i = 2; i * i < M; i++)
    for (int j = 1; j * i * i < M; j++) mu[i * i * j] = 0;
  for (int i = 1; i < M; i++)
    for (int j = 1; j * i < M; j++) p[i * j][i] = 1, Mu[i][i * j] = mu[j];
}
signed main() {
  pre();
  n = read();
  m = read();
  for (int i = 1; i <= m; i++) {
    int op = read();
    if (op == 1) {
      int x = read(), v = read();
      a[x] = p[v];
    } else if (op == 2) {
      int x = read(), y = read(), z = read();
      a[x] = a[y] ^ a[z];
    } else if (op == 3) {
      int x = read(), y = read(), z = read();
      a[x] = a[y] & a[z];
    } else if (op == 4) {
      int x = read(), v = read();
      printf("%d", ((a[x] & Mu[v]).count() & 1));
    }
  }
  return 0;
}
