#include <bits/stdc++.h>
using namespace std;
constexpr int MAX_N = 100100;
constexpr int MAX_V = 7005;
int n, q;
bitset<MAX_V> base[MAX_V];
bitset<MAX_V> mask[MAX_V];
bitset<MAX_V> val[MAX_N];
void prt(int x) {}
int main() {
  scanf(" %d %d", &n, &q);
  for (int i = 1; i < MAX_V; ++i) {
    for (int j = i; j < MAX_V; j += i) {
      base[j][i] = 1;
    }
  }
  for (int i = MAX_V - 1; i >= 1; --i) {
    mask[i][i] = 1;
    for (int j = 2 * i; j < MAX_V; j += i) {
      mask[i] = mask[i] ^ mask[j];
    }
  }
  for (int it = 0; it < q; ++it) {
    int typ;
    scanf(" %d", &typ);
    if (typ == 1) {
      int x, v;
      scanf(" %d %d", &x, &v);
      val[x] = base[v];
      prt(x);
    } else if (typ == 2) {
      int x, y, z;
      scanf(" %d %d %d", &x, &y, &z);
      val[x] = val[y] ^ val[z];
      prt(x);
    } else if (typ == 3) {
      int x, y, z;
      scanf(" %d %d %d", &x, &y, &z);
      val[x] = val[y] & val[z];
      prt(x);
    } else if (typ == 4) {
      int x, v;
      scanf(" %d %d", &x, &v);
      bitset<MAX_V> ans = val[x] & mask[v];
      printf("%d", (int)(ans.count() & 1));
      prt(x);
    }
  }
  printf("\n");
  return 0;
}
