#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 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;

struct custom_bitset {
  vector<uint64_t> bits;
  int64_t b, n;

  custom_bitset(int64_t _b = 0) {
    init(_b);
  }
 
  void init(int64_t _b) {
    b = _b;
    n = (b + 63) >> 6;
    bits.assign(n, 0);
  }
  
  void kuo(int64_t _b) {
    b = _b;
    n = (b + 63) >> 6;
    while (int(bits.size()) < n) bits.push_back(0LLU);
  }

  void clear() {
    b = n = 0;
    bits.clear();
  }

  void reset() {
    bits.assign(n, 0);
  }
  
  void set() {
    bits.assign(n, -1LLU);
    if (b != 64 * n)
      bits.back() &= (1LLU << (b - 64 * (n - 1))) - 1;
  }
 
  void _clean() {
    // Reset all bits after `b`.
    if (b != 64 * n)
      bits.back() &= (1LLU << (b - 64 * (n - 1))) - 1;
  }
 
  void change(int64_t index) {
    bits[index >> 6] ^= (1LLU << (index & 63));
  }
  
  int64_t count() const {
    int64_t sum = 0;
    for (int i = 0; i < n; i++)
      sum += __builtin_popcountll(bits[i]);
    return sum;
  }
 
  custom_bitset& operator&=(const custom_bitset &other) {
    assert(b == other.b);
 
    for (int i = 0; i < n; i++)
      bits[i] &= other.bits[i];
 
    return *this;
  }
};

const int maxn = 1000010;

struct node {
  ull x;
  int op, ans;
} a[maxn];

int n, m, rnk[maxn], tot, ST;
custom_bitset st[4][1 << 8], res;

int main() {
  ST = clock();
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n >> m;
  rep (i, 1, m) {
    char ch;
    cin >> ch >> a[i].x, a[i].ans = 0;
    a[i].op = (ch == '!');
  }
  rep (i, 1, m) {
    if (i % 10 == 0 && clock() - ST > 4.5 * CLOCKS_PER_SEC) break;
    if (a[i].op) {
      rnk[i] = tot++;
      rep (i, 0, 3) rep (j, 0, (1 << 8) - 1) st[i][j].kuo(tot);
      rep (j, 0, 3) {
        ull msk = ((a[i].x >> (j << 3)) & ((1 << 8) - 1)) ^ ((1 << 8) - 1);
        for (ull s = msk; ; s = (s - 1) & msk) {
          st[j][((1 << 8) - 1) ^ s].change(rnk[i]);
          if (!s) break;
        }
      }
    } else if (tot) {
      res.init(tot), res.set();
      rep (j, 0, 3) {
        ull msk = ((a[i].x >> (j << 3)) & ((1 << 8) - 1));
        res &= st[j][msk];
      }
      a[i].ans = (res.count() & 1);
    }
  }
  rep (i, 1, m) if (!a[i].op) cout << a[i].ans << '\n';
}