#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &a) {
  return os << '(' << a.first << ", " << a.second << ')';
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) {
  os << '[';
  for (unsigned int i = 0; i < a.size(); i++)
    os << a[i] << (i < a.size() - 1 ? ", " : "");
  os << ']';
  return os;
}
int primes[7005];
void eratosthene() {
  for (int i = 2; i <= 7005 - 5; i++)
    if (primes[i] == 0)
      for (int j = i; j <= 7005 - 5; j += i) primes[j] = i;
}
int cache[7005];
bool isSqrFree(int X) {
  int &ret = cache[X];
  if (ret != -1) return ret;
  ret = false;
  while (X > 1) {
    int val = primes[X];
    int cnt = 0;
    while (primes[X] == val) {
      X /= val;
      cnt++;
      if (cnt == 2) return ret = false;
    }
  }
  return ret = true;
}
int n, q;
bitset<7001> a[N];
bitset<7001> type1[7001];
bitset<7001> type4[7001];
void prep() {
  eratosthene();
  memset(cache, -1, sizeof(cache));
  for (int i = (int)1; i <= (int)7000; i++) {
    for (int j = 1; i * j <= 7000; j++) {
      if (isSqrFree(j)) type4[i][i * j] = 1;
      type1[i * j][i] = 1;
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  prep();
  cin >> n >> q;
  for (int i = (int)1; i <= (int)q; i++) {
    int type;
    cin >> type;
    if (type == 1) {
      int x, v;
      cin >> x >> v;
      a[x] = type1[v];
    } else if (type == 2) {
      int x, y, z;
      cin >> x >> y >> z;
      a[x] = (a[y] ^ a[z]);
    } else if (type == 3) {
      int x, y, z;
      cin >> x >> y >> z;
      a[x] = (a[y] & a[z]);
    } else {
      int x, v;
      cin >> x >> v;
      bitset<7001> tmp = (a[x] & type4[v]);
      cout << tmp.count() % 2;
    }
  }
}
