#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
int const N = 1e5 + 20, MAX = 7000 + 20;
int n, q;
bitset<MAX> bt[N];
int a[MAX];
vector<int> dv[MAX];
bitset<MAX> save[MAX];
void pre() {
  a[1] = 1;
  for (int i = 1; i < MAX; i++) {
    for (int j = 2 * i; j < MAX; j += i) a[j] ^= a[i], dv[j].push_back(i);
    dv[i].push_back(i);
  }
  for (int i = 1; i < MAX; i++) {
    for (int j = 1; i * j < MAX; j++) {
      if (a[j]) save[i][i * j] = 1;
    }
  }
}
int main() {
  pre();
  scanf("%d %d ", &n, &q);
  while (q--) {
    int tp, x, y, z, v;
    scanf("%d ", &tp);
    if (tp == 1) {
      scanf("%d %d ", &x, &v);
      x--;
      bt[x].reset();
      for (int u : dv[v]) bt[x][u] = 1;
    } else if (tp == 2) {
      scanf("%d %d %d ", &x, &y, &z);
      x--, y--, z--;
      bt[x] = (bt[y] ^ bt[z]);
    } else if (tp == 3) {
      scanf("%d %d %d ", &x, &y, &z);
      x--, y--, z--;
      bt[x] = (bt[y] & bt[z]);
    } else if (tp == 4) {
      scanf("%d %d ", &x, &v);
      x--;
      bitset<MAX> tmp = (bt[x] & save[v]);
      putchar('0' + (tmp.count() & 1));
    }
  }
  putchar('\n');
}
