#include <bits/stdc++.h>
using namespace std;
const int MN = 1e5 + 111, MT = 7001;
bitset<MT> r[MN];
bitset<MT> prep[MT], prepmask[MT];
int sq[MT];
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  for (int i = 1; i < MT; ++i) {
    for (int j = i; j < MT; j += i) {
      prep[j][i] = 1;
    }
  }
  for (int i = 2; i < MT; i++) {
    for (int k = 2; k * k < MT; ++k) {
      if (i % (k * k) == 0) sq[i] = 1;
    }
  }
  for (int i = 1; i < MT; ++i) {
    for (int j = i; j < MT; j += i) {
      if (sq[j / i]) continue;
      prepmask[i][j] = 1;
    }
  }
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < q; ++i) {
    int t;
    cin >> t;
    if (t == 1) {
      int first, v;
      cin >> first >> v;
      first--;
      r[first] = prep[v];
    } else if (t == 2) {
      int first, second, z;
      cin >> first >> second >> z;
      first--;
      second--;
      z--;
      r[first] = r[second] ^ r[z];
    } else if (t == 3) {
      int first, second, z;
      cin >> first >> second >> z;
      first--;
      second--;
      z--;
      r[first] = r[second] & r[z];
    } else {
      int first, v;
      cin >> first >> v;
      first--;
      cout << (((r[first] & prepmask[v]).count()) & 1);
    }
  }
}
