#include <bits/stdc++.h>
using namespace std;
long long mod = (1000000007LL);
inline long long poww(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return res;
}
inline pair<int, int> operator+(pair<int, int> A, pair<int, int> B) {
  return pair<int, int>(A.first + B.first, A.second + B.second);
}
inline pair<int, int> operator-(pair<int, int> A, pair<int, int> B) {
  return pair<int, int>(A.first - B.first, A.second - B.second);
}
inline long long mult(long long a, long long b) { return (a * b) % mod; }
long long gcd(long long a, long long b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
int n, m, q, k, v[100050], ans;
pair<int, int> w[100050];
string second;
class multiplicative {
 public:
  int T(int p, int k, int pk) { return (k == 0 ? 1 : 0) - (k == 1 ? 1 : 0); }
  void sieve(int n) {
    for (int j = 2; j < n; j++) {
      if (!is_composite[j])
        primes.push_back(j), cnt[j] = 1, sp[j] = j, func[j] = T(j, cnt[j], j);
      for (int i = 0; i < primes.size() && primes[i] * j < n; i++) {
        is_composite[primes[i] * j] = true;
        if (j % primes[i] == 0) {
          cnt[primes[i] * j] = cnt[j] + 1,
                          sp[primes[i] * j] = sp[j] * primes[i];
          func[primes[i] * j] =
              func[j / sp[j]] * T(primes[i], cnt[j] + 1, sp[primes[i] * j]);
          break;
        } else {
          func[primes[i] * j] = func[primes[i]] * func[j];
          cnt[primes[i] * j] = 1, sp[primes[i] * j] = primes[i];
        }
      }
    }
  }
  void init(int n) {
    is_composite.assign(n, 0), cnt.assign(n, 0), func.assign(n, 0),
        sp.assign(n, 0), func[1] = 1;
    sieve(n);
  }
  inline int get(int x) { return func[x]; }

 private:
  vector<bool> is_composite;
  vector<int> primes, cnt, func, sp;
};
bitset<7001> uni[7001], mi[7001], blank, S[100050];
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> q;
  multiplicative M;
  M.init(9000);
  for (int i = 1; i <= 7000; i++) {
    for (int j = i; j <= 7000; j += i) {
      mi[i][j] = M.get(j / i);
      uni[j][i] = 1;
    }
  }
  while (q--) {
    int op, a, b, c;
    cin >> op;
    if (op == 1) {
      cin >> a >> b;
      S[a] = uni[b];
    } else if (op == 2) {
      cin >> a >> b >> c;
      S[a] = (S[b] ^ S[c]);
    } else if (op == 3) {
      cin >> a >> b >> c;
      S[a] = (S[b] & S[c]);
    } else {
      cin >> a >> b;
      cout << ((S[a] & mi[b]).count()) % 2;
    }
  }
}
