#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10, inf = 1e9 + 10, maxv = 7000 + 10;
int n, q;
bitset<maxv> S[maxn], dp[maxv], tmp;
vector<int> p[maxv];
void sieve() {
  for (int i = 1; i < maxv; i++) {
    for (int j = i; j < maxv; j += i) {
      p[j].push_back(i);
    }
  }
}
int32_t main() {
  sieve();
  dp[1][1] = 1;
  for (int i = 2; i < maxv; i++) {
    for (int x : p[i]) {
      if (x < i) {
        dp[1][i] = dp[1][i] ^ dp[1][x];
      }
    }
  }
  for (int i = 2; i < maxv; i++) {
    for (int j = i; j < maxv; j += i) {
      dp[i][j] = dp[1][j / i];
    }
  }
  scanf("%d%d", &n, &q);
  for (int step = 0; step < q; step++) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int x, v;
      scanf("%d%d", &x, &v);
      S[x].reset();
      for (int v0 : p[v]) {
        S[x][v0] = 1;
      }
    }
    if (t == 2) {
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      S[x] = S[y] ^ S[z];
    }
    if (t == 3) {
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      S[x] = S[y] & S[z];
    }
    if (t == 4) {
      int x, v;
      scanf("%d%d", &x, &v);
      tmp = S[x] & dp[v];
      printf("%d", (int(tmp.count()) & 1));
    }
  }
  printf("\n");
}
