#include <bits/stdc++.h>
using namespace std;
int P1 = 1000000, P2 = 0;
char buf[1000005], wb[1000005];
int gc() {
  if (P1 >= 1000000) fread(buf, 1, 1000000, stdin), P1 = 0;
  return buf[P1++];
}
long long getint() {
  long long ret = 0, flag = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') flag = -1;
    c = getchar();
  }
  while (c <= '9' && c >= '0') {
    ret = (ret << 3) + (ret << 1) + c - '0';
    c = getchar();
  }
  return ret * flag;
}
void pc(char x) {
  if (P2 >= 1000000) fwrite(wb, 1, 1000000, stdout), P2 = 0;
  wb[P2++] = x;
}
void wrt(long long x) {
  if (x < 0) pc('-'), x = -x;
  int c[24] = {0};
  if (!x) return pc('0'), void();
  while (x) c[++c[0]] = x % 10, x /= 10;
  while (c[0]) pc(c[c[0]--] + '0');
}
int n, m;
bool vst[7005];
int prim[7005], mul[7005];
bitset<7005> G[7005], M[7005], S[100005];
int main() {
  mul[1] = 1;
  for (int i = 2; i <= 7000; i++) {
    if (!vst[i]) prim[++prim[0]] = i, mul[i] = -1;
    for (int j = 1; j <= prim[0] && prim[j] * i <= 7000; j++) {
      int x = prim[j] * i;
      vst[x] = 1;
      if (i % prim[j] == 0) break;
      mul[x] = -mul[i];
    }
  }
  for (int i = 1; i <= 7000; i++) {
    for (int j = i; j <= 7000; j += i) G[j][i] = 1, M[i][j] = mul[j / i] != 0;
  }
  n = getint();
  m = getint();
  for (int i = 1; i <= m; i++) {
    int opt = getint();
    if (opt == 1) {
      int x = getint(), val = getint();
      S[x] = G[val];
    }
    if (opt == 2) {
      int x = getint(), y = getint(), z = getint();
      S[x] = S[y] ^ S[z];
    }
    if (opt == 3) {
      int x = getint(), y = getint(), z = getint();
      S[x] = S[y] & S[z];
    }
    if (opt == 4) {
      int x = getint(), val = getint();
      pc(((M[val] & S[x]).count() & 1) ^ 48);
    }
  }
  fwrite(wb, 1, P2, stdout);
  return 0;
}
