#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, w = 0;
  char c = getchar();
  while (!isdigit(c)) w |= c == '-', c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return w ? -x : x;
}
namespace star {
const int maxn = 1e5 + 10, maxm = 7005, M = 7000;
bitset<maxm> f[maxm], g[maxm], a[maxn];
int n, m, mu[maxn], p[maxn], tot;
bool mark[maxn];
inline void pre() {
  mu[1] = 1;
  for (int i = 2; i <= M; i++) {
    if (!mark[i]) p[++tot] = i, mu[i] = 1;
    for (int tmp, j = 1; j <= tot and (tmp = i * p[j]) <= M; j++) {
      mark[tmp] = true;
      if (i % p[j] == 0) break;
      mu[tmp] = mu[i];
    }
  }
  for (int i = 1; i <= M; i++)
    for (int j = i; j <= M; j += i) f[j][i] = 1, g[i][j] = mu[j / i];
}
inline void work() {
  n = read(), m = read();
  int x, y, z;
  while (m--) switch (read()) {
      case 1:
        x = read(), y = read(), a[x] = f[y];
        break;
      case 2:
        x = read(), y = read(), z = read(), a[x] = a[y] ^ a[z];
        break;
      case 3:
        x = read(), y = read(), z = read(), a[x] = a[y] & a[z];
        break;
      case 4:
        x = read(), y = read(), printf("%d", (int)(a[x] & g[y]).count() % 2);
    }
}
}  // namespace star
signed main() {
  star::pre();
  star::work();
  return 0;
}
