#ifdef LOCAL
#include "stdafx.h"
#else
#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define sz(v) ((int) (v).size())
#define me(f, x) memset(f, x, sizeof(f))
#define mc(f, g) memcpy(f, g, sizeof(g))
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;

using vi = vector<int>;
#endif

#ifdef _WIN32
using uint = unsigned;
#endif
using ull = unsigned long long;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

constexpr int N = 1e6 + 9;
constexpr int LIM = 50;
int n, m;

uint sup (uint x) {
  return (1U << (n - 6)) - x - 1;
}

struct Q {
  uint x; ull y;
} q[N];

uint A, B, C;

uint cost_qry (uint x) {
  return 1U << __builtin_popcount((x & A) | (sup(x) & C));
}

uint cost_mdy (uint x) {
  return 1U << __builtin_popcount((sup(x) & B) | (x & C));
}

ull a[1U << 26];

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  L (i, 1, m) {
    char o[3];
    uint x;
    cin >> o >> x;
    if (*o == '!') {
      uint s = x & ((1 << 6) - 1);
      q[i].x = x >> 6;
      for (uint t = s; t < 64; t = (t + 1) | s) {
        q[i].y ^= 1ULL << t;
      }
    } else {
      q[i].x = x;
    }
  }
  uint X = 0, Y = 0, Z = 0;
  ull cost = LONG_LONG_MAX;
  L (r, 0, LIM - 1) {
    A = B = C = 0;
    L (i, 0, n - 1) {
      int o = rng() % 3;
      (o ? (o & 1 ? B : C) : A) |= 1U << i;
    }
    ull cur = 0;
    L (i, 1, m) {
      cur += q[i].y ? cost_mdy(q[i].x) : cost_qry(q[i].x >> 6);
    }
    if (cur < cost) {
      cost = cur;
      X = A;
      Y = B;
      Z = C;
    }
  }
  A = X;
  B = Y;
  C = Z;
  cerr << cost << '\n';
  L (i, 1, m) {
    if (q[i].y) {
      uint x = q[i].x;
      uint s = (sup(x) & B) | (x & C), r = x & (A | B);
      for (uint t = s; ; t = (t - 1) & s) {
        a[t | r] ^= q[i].y;
        if (!t) {
          break;
        }
      }
    } else {
      uint x = q[i].x >> 6, c = q[i].x & ((1 << 6) - 1);
      uint s = (x & A) | (sup(x) & C), r = x & B;
      uint y = 0;
      for (uint t = s; ; t = (t - 1) & s) {
        y += a[t | r];
        if (!t) {
          break;
        }
      }
      cout.put('0' | (y >> c & 1)), cout.put('\n');
    }
  }
}
// I love WHQ!