#include <bits/stdc++.h>
using namespace std;
const int N = 7001, MAXN = 100001;
int n, Q;
bitset<N> que[N], st[MAXN];
vector<int> d[N];
int pri[N + 233], mip[N + 233], mu[N + 233], pcn;
void first() {
  mu[1] = 1;
  for (int i = 2; i < N; i++) {
    if (!mip[i]) pri[++pcn] = i, mu[i] = -1;
    for (int j = 1; j <= pcn && i * pri[j] < N; j++) {
      mip[i * pri[j]] = pri[j];
      if (i % pri[j] == 0) break;
      mu[i * pri[j]] = -mu[i];
    }
  }
  for (int i = 1; i < N; i++)
    for (int j = i; j < N; j += i)
      if (mu[j / i]) que[i][j] = 1;
  for (int i = 1; i < N; i++)
    for (int j = i; j < N; j += i) d[j].push_back(i);
}
int main() {
  first();
  scanf("%d%d", &n, &Q);
  while (Q--) {
    int opt, x, y, z, v;
    scanf("%d", &opt);
    switch (opt) {
      case 1:
        scanf("%d%d", &x, &v);
        st[x].reset();
        for (int t : d[v]) st[x][t] = 1;
        break;
      case 2:
        scanf("%d%d%d", &x, &y, &z);
        st[x] = st[y] ^ st[z];
        break;
      case 3:
        scanf("%d%d%d", &x, &y, &z);
        st[x] = st[y] & st[z];
        break;
      case 4:
        scanf("%d%d", &x, &v);
        putchar((st[x] & que[v]).count() & 1 ? '1' : '0');
        break;
    }
  }
  return puts(""), 0;
}
