#include <algorithm>
#include <bitset>
#include <cctype>
#include <ctime>
#include <random>
using namespace std;
mt19937 rng(2007329);
typedef unsigned int ui;
typedef unsigned long long ull;
const int M = 1000003;
#define getchar()                                                              \
    (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 22, stdin)),            \
     p1 == p2 ? EOF : *p1++)
char buf[1 << 22], *p1 = buf, *p2 = buf;
ui read() {
    char c = getchar();
    ui x = 0;
    while (!isdigit(c))
        c = getchar();
    do
        x = x * 10 + (c ^ 48), c = getchar();
    while (isdigit(c));
    return x;
}
bool op[M];
int mn = 0x3f3f3f3f;
ui n, q, ps[M], cur, loc[3], tmp[3];
ull f[1 << 26], msk[64];
ui calc() {
    ui sum = 0;
    for (int i = 0; i < q; ++i) {
        ui now = 1;
        if (op[i]) {
            now <<= __builtin_popcount(tmp[2] & ps[i]);
            now <<= __builtin_popcount(tmp[1] & ~ps[i]);
        } else {
            now <<= __builtin_popcount(tmp[0] & ps[i]);
            now <<= __builtin_popcount(tmp[2] & ~ps[i]);
        }
        sum += now;
    }
    return sum;
}
int main() {
    for (ui i = 0; i < 64; ++i)
        for (ui j = 0; j < 64; ++j)
            if ((i & j) == j)
                msk[i] |= (1llu << j);
    n = read(), q = read();
    for (int i = 0; i < q; ++i) {
        char cc = getchar();
        while (cc != '!' and cc != '?')
            cc = getchar();
        op[i] = (cc == '!'), ps[i] = read();
    }
    for (int it = 0; it < 10; ++it) {
        tmp[0] = tmp[1] = tmp[2] = 0;
        for (int x = 6; x < n; ++x)
            tmp[rng() % 3] |= (1u << x);
        ui sum = calc();
        if (mn > sum)
            mn = sum, loc[0] = tmp[0], loc[1] = tmp[1], loc[2] = tmp[2];
    }
    ui las = mn;
    tmp[0] = loc[0], tmp[1] = loc[1], tmp[2] = loc[2];
    for (int it = 0; it < 25; ++it) {
        int x = rng() % (n - 6) + 6;
        int sp = -1;
        if (tmp[0] >> x & 1)
            tmp[0] ^= (1u << x), sp = 0;
        if (tmp[1] >> x & 1)
            tmp[1] ^= (1u << x), sp = 1;
        if (tmp[2] >> x & 1)
            tmp[2] ^= (1u << x), sp = 2;
        int pp = rng() % 3;
        while (pp == sp)
            pp = rng() % 3;
        tmp[pp] ^= (1u << x);
        ui now = calc();
        if (mn > now)
            mn = now, loc[0] = tmp[0], loc[1] = tmp[1], loc[2] = tmp[2];
        if (now > las and (rng() & 7))
            tmp[sp] ^= (1u << x), tmp[pp] ^= (1u << x);
        else
            las = now;
    }
    for (int i = 0; i < q; ++i)
        if (op[i]) {
            ui now = (loc[2] & ps[i]) | (loc[1] & ~ps[i]);
            ull val = 1llu << (ps[i] & 63);
            ps[i] >>= 6, now >>= 6;
            for (ui x = now;; x = (x - 1) & now) {
                f[ps[i] ^ x] ^= val;
                if (!x)
                    break;
            }
        } else {
            ui now = (loc[0] & ps[i]) | (loc[2] & ~ps[i]);
            ps[i] &= ~loc[2];
            bool res = 0;
            ull val = msk[ps[i] & 63];
            ps[i] >>= 6, now >>= 6;
            for (ui x = now;; x = (x - 1) & now) {
                res ^= __builtin_parityll(f[ps[i] ^ x] & val);
                if (!x)
                    break;
            }
            printf("%d\n", res);
        }
    return 0;
}