#include <bits/stdc++.h>
using namespace std;
const int M = 7002;
const int N = 100010;
int n, q;
bitset<M> num[M];
bitset<M> sq[M];
bitset<M> a[N];
vector<int> squareFree;
int main() {
  cin >> n >> q;
  for (int i = 1; i < M; ++i) {
    int good = 1;
    for (int j = 2; j * j <= i; ++j) {
      if (i % (j * j) == 0) {
        good = 0;
        break;
      }
    }
    if (good) squareFree.push_back(i);
  }
  for (int i = 1; i < M; ++i) {
    for (int j = 1; j * j <= i; ++j) {
      if (i % j == 0) {
        num[i][j] = num[i][i / j] = 1;
      }
    }
  }
  for (int i = 1; i < M; ++i) {
    for (int j : squareFree) {
      if (i * j > 7000) break;
      sq[i][i * j] = 1;
    }
  }
  while (q--) {
    int cmd, x, y, z, v;
    scanf("%d %d", &cmd, &x);
    if (cmd == 1) {
      scanf("%d", &v);
      a[x] = num[v];
    } else if (cmd == 2) {
      scanf("%d %d", &y, &z);
      a[x] = a[y] ^ a[z];
    } else if (cmd == 3) {
      scanf("%d %d", &y, &z);
      a[x] = a[y] & a[z];
    } else {
      scanf("%d", &v);
      int ans = (sq[v] & a[x]).count() % 2;
      printf("%d", ans);
    }
  }
  puts("");
  return 0;
}
