#include <bits/stdc++.h>
using namespace std;
int N, M, tot, prm[7001], mu[7001];
bool Not[7001];
bitset<7001> a[100001], b[7001], val[7001];
int main() {
  N = 7001 - 1;
  mu[1] = 1;
  for (int i = 2; i <= N; i++) {
    if (!Not[i]) prm[++tot] = i, mu[i] = -1;
    for (int j = 1; j <= tot && i * prm[j] <= N; j++) {
      Not[i * prm[j]] = 1;
      if (i % prm[j] == 0) break;
      mu[i * prm[j]] = -mu[i];
    }
  }
  for (int i = 1; i <= N; i++)
    for (int j = i; j <= N; j += i) b[i][j] = mu[j / i] != 0, val[j][i] = 1;
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= M; i++) {
    int opt, x, y, z;
    scanf("%d%d%d", &opt, &x, &y);
    if (opt == 2 || opt == 3) scanf("%d", &z);
    if (opt == 1)
      a[x] = val[y];
    else if (opt == 2)
      a[x] = a[y] ^ a[z];
    else if (opt == 3)
      a[x] = a[y] & a[z];
    else
      putchar(((a[x] & b[y]).count() & 1) + '0');
  }
  return 0;
}
