#include <bits/stdc++.h>
using namespace std;
bitset<7000 + 5> fac[7000 + 5], fy[7000 + 5], a[100000 + 5];
int miu[7000 + 5];
int main() {
  for (int i = 1; i <= 7000; i++) {
    for (int j = i; j <= 7000; j += i) fac[j].set(i);
  }
  for (int i = 1; i <= 7000; i++) miu[i] = 1;
  for (int i = 2; i <= 7000; i++) {
    for (int j = i * i; j <= 7000; j += i * i) miu[j] = 0;
  }
  for (int i = 1; i <= 7000; i++) {
    for (int j = i; j <= 7000; j += i) fy[i].set(j, miu[j / i]);
  }
  int n, q;
  scanf("%d%d", &n, &q);
  while (q--) {
    int opt;
    scanf("%d", &opt);
    if (opt == 1) {
      int x, v;
      scanf("%d%d", &x, &v);
      a[x] = fac[v];
    }
    if (opt == 2) {
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      a[x] = a[y] ^ a[z];
    }
    if (opt == 3) {
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      a[x] = a[y] & a[z];
    }
    if (opt == 4) {
      int x, v;
      scanf("%d%d", &x, &v);
      printf("%d", (a[x] & fy[v]).count() & 1);
    }
  }
  puts("");
  return 0;
}
