#include <bits/stdc++.h>
using namespace std;
const int MAXV = 7100;
class Solution {
  vector<bitset<MAXV>> mob, take, hand;
  int n, q;

 public:
  void run(istream &in, ostream &out) {
    in >> n >> q;
    hand.resize(n + 1);
    mob.resize(MAXV);
    take.resize(MAXV);
    mob[1].flip();
    mob[1].flip(0);
    for (int i = 2; i * i < MAXV; ++i) {
      for (int j = i * i; j < MAXV; j += i * i) mob[1][j] = 0;
    }
    for (int i = 1; i < MAXV; ++i) {
      for (int j = i; j < MAXV; j += i) {
        mob[i][j] = mob[1][j / i];
        take[j][i] = 1;
      }
    }
    for (int i = 0; i < q; ++i) {
      int t, x, y, z;
      in >> t >> x >> y;
      if (t == 1) {
        hand[x] = take[y];
      } else if (t == 2) {
        in >> z;
        hand[x] = hand[y] ^ hand[z];
      } else if (t == 3) {
        in >> z;
        hand[x] = hand[y] & hand[z];
      } else
        out << ((hand[x] & mob[y]).count() & 1);
    }
    out << '\n';
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  Solution().run(cin, cout);
}
