#include <bits/stdc++.h>
using namespace std;
const int MX = 7010;
int mu[MX];
bitset<MX> divs[MX];
bitset<MX> pat[MX];
void pre() {
  for (int i = 1; i < MX; i++)
    for (int j = i; j < MX; j += i) divs[j][i] = 1;
  fill(mu, mu + MX, 1);
  for (int i = 2; i * i < MX; i++)
    for (int j = i * i; j < MX; j += i * i) mu[j] = 0;
  for (int i = 1; i < MX; i++)
    for (int j = i; j < MX; j += i)
      if (mu[j / i]) pat[i][j] = 1;
}
const int N = 1e5 + 7;
bitset<MX> bs[N];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  pre();
  int n, q;
  cin >> n >> q;
  while (q--) {
    int t;
    cin >> t;
    if (t == 1) {
      int x, v;
      cin >> x >> v;
      bs[x] = divs[v];
    }
    if (t == 2) {
      int x, y, z;
      cin >> x >> y >> z;
      bs[x] = bs[y] ^ bs[z];
    }
    if (t == 3) {
      int x, y, z;
      cin >> x >> y >> z;
      bs[x] = bs[y] & bs[z];
    }
    if (t == 4) {
      int x, v;
      cin >> x >> v;
      bitset<MX> ans = pat[v] & bs[x];
      cout << ans.count() % 2;
    }
  }
}
