#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
const int N = 7e3 + 5;
const int M = 1e5 + 5;
bitset<N> bi[M], mu[N], G[N];
bool vis[N];
int prime[N], Mu[N];
int main() {
  Mu[1] = 1;
  for (int i = 2, pnum = 0; i < N; ++i) {
    if (!vis[i]) {
      prime[++pnum] = i;
      Mu[i] = 1;
    }
    for (int j = 1; j <= pnum && prime[j] * i < N; ++j) {
      vis[prime[j] * i] = true;
      if (i % prime[j] == 0)
        Mu[prime[j] * i] = 0;
      else
        Mu[prime[j] * i] = -Mu[i];
    }
  }
  for (int i = 1; i < N; ++i) {
    for (int j = i; j < N; j += i) {
      G[j][i] = 1;
      mu[i][j] = (Mu[j / i] != 0);
    }
  }
  int n, q;
  scanf("%d %d", &n, &q);
  while (q--) {
    int op, x, y, z, v;
    scanf("%d %d %d", &op, &x, &y);
    if (op == 1) {
      bi[x] = G[y];
    } else if (op == 2) {
      scanf("%d", &z);
      bi[x] = bi[y] ^ bi[z];
    } else if (op == 3) {
      scanf("%d", &z);
      bi[x] = bi[y] & bi[z];
    } else {
      putchar(((bi[x] & mu[y]).count() & 1) ? '1' : '0');
    }
  }
}
