#include <bits/stdc++.h>
using namespace std;
const int N = 100001, V = 7001, Q = 1000001;
int n, q;
bool is_prime[V];
int prime[V], mu[V], cnt = 0;
bitset<V> a[N], b[V];
void init() {
  for (int i = 1; i < V; i++) is_prime[i] = (i != 1);
  mu[1] = 1;
  for (int i = 2; i < V; i++) {
    if (is_prime[i]) prime[++cnt] = i, mu[i] = -1;
    for (int j = 1; j <= cnt && i * prime[j] < V; j++) {
      is_prime[i * prime[j]] = false;
      if (i % prime[j])
        mu[i * prime[j]] = -mu[i];
      else {
        mu[i * prime[j]] = 0;
        break;
      }
    }
  }
  for (int i = 1; i < V; i++) {
    for (int j = i; j < V; j += i)
      if (mu[j / i]) b[i][j] = 1;
  }
}
char str[Q];
int tot = 0;
int main() {
  scanf("%d%d", &n, &q);
  init();
  for (int i = 1; i <= q; i++) {
    int type;
    scanf("%d", &type);
    if (type == 1) {
      int x, v;
      scanf("%d%d", &x, &v);
      a[x].reset();
      for (int i = 1; i * i <= v; i++) {
        if (v % i == 0) {
          a[x][i] = 1;
          if (i * i < v) a[x][v / i] = 1;
        }
      }
    } else if (type == 2) {
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      a[x] = a[y] ^ a[z];
    } else if (type == 3) {
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      a[x] = a[y] & a[z];
    } else if (type == 4) {
      int x, v;
      scanf("%d%d", &x, &v);
      str[tot++] = (char)('0' + ((a[x] & b[v]).count() & 1));
    }
  }
  for (int i = 0; i < tot; i++) printf("%c", str[i]);
  printf("\n");
  return 0;
}
