#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 1000010;
const int A = 6;
mt19937 rnd(random_device{}());

struct node {
  int op;
  uint x;
} a[maxn];

ull buc[1 << 26], ca[maxn], val[64], mn;
int n, m, p[maxn], k0, k1, k2, bits[32];

uint gao(uint x) {
  rep (i, 0, n - 1) bits[i] = (x >> i & 1);
  uint res = 0;
  rep (i, 0, n - 1) if (p[i] == 2) res = res << 1 | bits[i];
  rep (i, 0, n - 1) if (p[i] == 1) res = res << 1 | bits[i];
  rep (i, 0, n - 1) if (p[i] == 0) res = res << 1 | bits[i];
  rep (i, 0, n - 1) if (p[i] == 3) res = res << 1 | bits[i];
  return res;
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  rep (s, 0, 63) rep (t, 0, 63) if ((s & t) == s) val[s] ^= (1ull << t);
  cin >> n >> m;
  rep (i, 1, m) {
    char ch;
    cin >> ch >> a[i].x;
    a[i].op = (ch == '!');
  }
  rep (i, 0, A - 1) p[i] = 0;
  rep (i, A, 2 * A - 1) p[i] = 1;
  rep (i, 2 * A, 25) p[i] = 2;
  rep (i, 26, 31) p[i] = 3;
  reverse(p, p + 32);
  shuffle(p + 6, p + 32, rnd);
  rep (i, 0, n - 1) {
    if (p[i] == 0) k0++;
    else if (p[i] == 1) k1++;
    else if (p[i] == 2) k2++;
  }
  rep (i, 1, m) ca[i] = a[i].x;
  mn = 1ull << 63;
  rep (_, 1, 10) {
    shuffle(p, p + n, rnd);
    rep (i, 1, m) a[i].x = gao(a[i].x);
    ull sum = 0;
    rep (i, 1, m) {
      if (a[i].op) {
        uint ax = a[i].x >> 6;
        uint x = ax & ((1u << k0) - 1);
        uint z = ax >> (k0 + k1);
        uint ix = ((1u << k0) - 1) ^ x;
        uint mask = ix | (z << (k0 + k1));
        sum += 1ull << __builtin_popcountll(mask);
      } else {
        uint ax = a[i].x >> 6;
        uint y = (ax >> k0) & ((1ull << k1) - 1);
        uint z = ax >> (k0 + k1);
        uint iz = ((1u << k2) - 1) ^ z;
        uint mask = (y << k0) | (iz << (k0 + k1));
        sum += 1ull << __builtin_popcountll(mask);
      }
    }
    if (sum < mn) {
      mn = sum;
      rep (i, 1, m) ca[i] = a[i].x;
    }
  }
  rep (i, 1, m) {
    if (a[i].op) {
      uint tp = ca[i] & 63, ax = ca[i] >> 6;
      uint x = ax & ((1u << k0) - 1);
      uint y = (ax >> k0) & ((1u << k1) - 1);
      uint z = ax >> (k0 + k1);
      uint ix = ((1u << k0) - 1) ^ x;
      uint mask = ix | (z << (k0 + k1));
      uint base = (y << k0) ^ ((1u << k0) - 1);
      for (uint s = mask; ; s = (s - 1) & mask) {
        buc[s ^ base] ^= val[tp];
        if (!s) break;
      }
    } else {
      uint tp = ca[i] & 63, ax = ca[i] >> 6;
      uint x = ax & ((1u << k0) - 1);
      uint y = (ax >> k0) & ((1ull << k1) - 1);
      uint z = ax >> (k0 + k1);
      uint iz = ((1u << k2) - 1) ^ z;
      uint mask = (y << k0) | (iz << (k0 + k1));
      ull res = 0;
      for (uint s = mask; ; s = (s - 1) & mask) {
        res ^= buc[s ^ x];
        if (!s) break;
      }
      cout << (res >> tp & 1) << '\n';
    }
  }
}