#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
bitset<7001> b[7001];
bitset<7001> lcm[7001];
bitset<7001> s[100005];
int mobe[7001];
int main() {
  fill(mobe + 1, mobe + 7001, 1);
  for (int i = 2; i < 7001; i++) {
    for (int j = 2; j < i; j++) {
      if (i % j == 0 && (i / j) % j == 0) {
        mobe[i] = 0;
        break;
      }
    }
  }
  for (int i = 1; i <= 7000; i++) {
    for (int j = 1; j <= i; j++) {
      if (i % j == 0) {
        b[i][j] = 1;
      }
    }
    for (int j = 1; i * j <= 7000; j++) {
      if (mobe[j]) lcm[i][i * j] = 1;
    }
  }
  int n, q;
  scanf("%d %d", &n, &q);
  while (q--) {
    int op;
    scanf("%d", &op);
    if (op == 1) {
      int first, v;
      scanf("%d %d", &first, &v);
      s[first] = b[v];
    } else if (op == 2) {
      int first, second, z;
      scanf("%d %d %d", &first, &second, &z);
      s[first] = s[second] ^ s[z];
    } else if (op == 3) {
      int first, second, z;
      scanf("%d %d %d", &first, &second, &z);
      s[first] = s[second] & s[z];
    } else {
      int first, v;
      scanf("%d %d", &first, &v);
      bitset<7001> temp = s[first] & lcm[v];
      int ans = temp.count() & 1;
      printf("%d", ans);
    }
  }
}
