#include <bits/stdc++.h>
using namespace std;
bitset<7005> d[7005], inv[7005], f[100005];
int n, Q;
int mul[7005], flag[7005], prime[7005], cnt;
int main() {
  scanf("%d%d", &n, &Q);
  mul[1] = 1;
  for (int i = 2; i <= 7000; i++) {
    if (!flag[i]) prime[++cnt] = i, mul[i] = -1;
    for (int j = 1; j <= cnt && prime[j] * i <= 7000; j++) {
      flag[prime[j] * i] = 1;
      mul[prime[j] * i] = -mul[i];
      if (i % prime[j] == 0) {
        mul[prime[j] * i] = 0;
        break;
      }
    }
  }
  for (int i = 1; i <= 7000; i++)
    for (int j = i; j <= 7000; j += i)
      d[j][i] = d[j][i] ^ 1, inv[i][j] = inv[i][j] ^ (mul[j / i] != 0);
  while (Q--) {
    int opt, x, y, z;
    scanf("%d%d%d", &opt, &x, &y);
    if (opt > 1 && opt < 4) scanf("%d", &z);
    if (opt == 1) f[x] = d[y];
    if (opt == 2) f[x] = f[y] ^ f[z];
    if (opt == 3) f[x] = f[y] & f[z];
    if (opt == 4) putchar('0' + ((f[x] & inv[y]).count() & 1));
  }
  puts("");
}
