#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, q;
bitset<7001> wz[N];
bitset<7001> xs[N], muu[N];
int mu[7010], p[7010], is[7010];
void init() {
  mu[1] = 1, n = 7000;
  for (int i = 2; i <= n; i++) {
    if (!is[i]) mu[i] = -1, p[++p[0]] = i;
    for (int j = 1; j <= p[0] && p[j] * i <= n; j++) {
      is[i * p[j]] = 1;
      mu[p[j] * i] = -mu[i];
      if (i % p[j] == 0) {
        mu[p[j] * i] = 0;
        break;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j += i) {
      xs[j][i] = 1;
      muu[i][j] = (mu[j / i] != 0);
    }
  }
}
int main() {
  init();
  cin >> n >> q;
  for (int w = 1; w <= q; w++) {
    int opt;
    scanf("%d", &opt);
    if (opt == 1) {
      int x, v;
      scanf("%d %d", &x, &v);
      wz[x] = 0;
      wz[x] = xs[v];
    } else if (opt == 2) {
      int x, y, z;
      scanf("%d %d %d", &x, &y, &z);
      wz[x] = wz[y] ^ wz[z];
    } else if (opt == 3) {
      int x, y, z;
      scanf("%d %d %d", &x, &y, &z);
      wz[x] = wz[y] & wz[z];
    } else if (opt == 4) {
      int x, v;
      scanf("%d %d", &x, &v);
      printf("%d", (wz[x] & muu[v]).count() & 1);
    }
  }
}
