#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e5 + 1;
const int C = 7070;
bitset<C> s[N];
bitset<C> divs[C], mu[C];
bool sqrFree(int x) {
  for (int d = 2; d * d <= x; ++d) {
    if (x % d) continue;
    x /= d;
    if (x % d == 0) return false;
  }
  return true;
}
int main() {
  for (int x = 1; x < C; ++x) {
    mu[1][x] = sqrFree(x);
    for (int i = 2; i * x < C; ++i) mu[i][i * x] = mu[1][x];
  }
  for (int x = 1; x < C; ++x) {
    for (int y = x; y < C; y += x) divs[y][x] = 1;
  }
  int n, q;
  scanf("%d %d", &n, &q);
  while (q--) {
    int type;
    scanf("%d", &type);
    if (type == 1) {
      int i, x;
      scanf("%d %d", &i, &x);
      s[i] = divs[x];
    }
    if (type == 2) {
      int i, j, k;
      scanf("%d %d %d", &i, &j, &k);
      s[i] = s[j] ^ s[k];
    }
    if (type == 3) {
      int i, j, k;
      scanf("%d %d %d\n", &i, &j, &k);
      s[i] = s[j] & s[k];
    }
    if (type == 4) {
      int i, x;
      scanf("%d %d\n", &i, &x);
      printf("%d", (s[i] & mu[x]).count() & 1);
    }
  }
}
