#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXB = 7005;
;
bitset<MAXB> a[MAXN], sf[MAXB], mua[MAXB];
int mu[MAXB], pa[MAXB], pn;
bool flag[MAXB];
int main() {
  int n, qn;
  mu[1] = 1;
  for (int i = 2; i < MAXB; ++i) {
    if (!flag[i]) pa[pn++] = i, mu[i] = -1;
    for (int j = 0; j < pn && pa[j] * i < MAXB; ++j) {
      flag[pa[j] * i] = true;
      if (i % pa[j] == 0) break;
      mu[pa[j] * i] = -mu[i];
    }
  }
  for (int i = 1; i < MAXB; ++i)
    for (int j = i; j < MAXB; ++j)
      if (j % i == 0) {
        sf[j].set(i);
        if (mu[j / i]) mua[i].set(j);
      }
  scanf("%d%d", &n, &qn);
  for (int qi = 0, t, x, y, z; qi < qn; ++qi) {
    scanf("%d%d%d", &t, &x, &y);
    switch (t) {
      case 1:
        a[x] = sf[y];
        break;
      case 2:
        scanf("%d", &z);
        a[x] = a[y] ^ a[z];
        break;
      case 3:
        scanf("%d", &z);
        a[x] = a[y] & a[z];
        break;
      default:
        printf("%c", (int)(mua[y] & a[x]).count() % 2 + '0');
    }
  }
  printf("\n");
  return 0;
}
