#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
int n, q, mu[7002];
bitset<7002> b[100005], ins[7002], qry[7002];
int get() {
  int x = 0;
  char c = getchar();
  while (c < 48) c = getchar();
  while (c > 47) x = x * 10 + c - 48, c = getchar();
  return x;
}
int main() {
  n = get();
  q = get();
  mu[1] = 1;
  for (int i = 1; i <= 7000; ++i) {
    ins[i][i] = 1;
    for (int j = i * 2; j <= 7000; j += i) {
      ins[j][i] = 1;
      mu[j] -= mu[i];
    }
  }
  for (int i = 1; i <= 7000; ++i) {
    mu[i] = (mu[i] % 2 + 2) % 2;
  }
  for (int i = 1; i <= 7000; ++i) {
    for (int j = i; j <= 7000; j += i) {
      if (mu[j / i] & 1) qry[i][j] = 1;
    }
  }
  for (int i = 1; i <= q; ++i) {
    int t, x, y, z;
    t = get();
    if (t == 1) {
      x = get();
      y = get();
      b[x] = ins[y];
    }
    if (t == 2) {
      x = get();
      y = get();
      z = get();
      b[x] = b[y] ^ b[z];
    }
    if (t == 3) {
      x = get();
      y = get();
      z = get();
      b[x] = b[y] & b[z];
    }
    if (t == 4) {
      x = get();
      y = get();
      int k = (b[x] & qry[y]).count();
      if (k & 1)
        putchar('1');
      else
        putchar('0');
    }
  }
  return 0;
}
