#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int f = 1, x = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const int MAXN = 100005;
const int MAXM = 7005;
bitset<MAXM> b1[MAXN], b2[MAXM], temp, G[MAXM];
int n, Q;
int mu[MAXM], pr[MAXM], plen;
bool vis[MAXM];
string ans;
void getmu(int N) {
  mu[1] = 1;
  for (int i = 2; i <= N; i++) {
    if (!vis[i]) pr[++plen] = i, mu[i] = -1;
    for (int j = 1; j <= plen && i * pr[j] <= N; j++) {
      vis[i * pr[j]] = true;
      if (!(i % pr[j])) {
        mu[i * pr[j]] = 0;
        break;
      }
      mu[i * pr[j]] = -mu[i];
    }
  }
}
int main() {
  getmu(MAXM - 5);
  for (int i = 1; i <= MAXM - 5; i++)
    for (int j = 1; j * i <= MAXM - 5; j++) {
      G[i * j][i] = 1;
      if (mu[j]) b2[i][i * j] = 1;
    }
  n = read();
  Q = read();
  while (Q--) {
    int opt = read(), u1 = read(), u2 = read();
    if (opt == 1) {
      b1[u1] = G[u2];
    } else if (opt == 2) {
      int u3 = read();
      b1[u1] = b1[u2] ^ b1[u3];
    } else if (opt == 3) {
      int u3 = read();
      b1[u1] = b1[u2] & b1[u3];
    } else {
      temp = b1[u1] & b2[u2];
      if (temp.count() & 1)
        ans += '1';
      else
        ans += '0';
    }
  }
  cout << ans;
  return 0;
}
