#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef unsigned int uint;

char *p1, *p2, buf[1048577];
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
template <typename T>
inline void Read(T &x)
{
    x = 0; char ch = gc;
    while (!isdigit(ch)) ch = gc;
    while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = gc;
}

bool getQ()
{
    char ch = gc;
    while (ch != '!' && ch != '?') ch = gc;
    return (ch == '!');
}

mt19937 rnd(time(0) ^ *(new unsigned long long));

ull vl[1 << 26];
int p[32], n;
bool w[32];
char s[5];

uint f(uint x)
{
    uint res = 0;
    for (int i = 0; i < n; i++) w[i] = (x >> i) & 1;
    for (int i = 0; i < n; i++) res |= (w[p[i]] << i);
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int q;
    Read(n), Read(q);
    for (int i = 0; i < n; i++) p[i] = i;
    shuffle(p, p + n, rnd);
    while (q--)
    {
        uint x, p;
        bool Fl = getQ(); Read(x); x = f(x);
        p = (x >> 6); ull v = 1ull << (x & 63);
        uint A = (p >> 16), B = (p >> 6) & 1023, C = p & 63;
        if (Fl)
        {
            uint D = B ^ 1023;
            for (uint st = D; ; st = (st - 1) & D)
            {
                for (uint ns = C; ; ns = (ns - 1) & C)
                {
                    vl[(A << 16) | ((st ^ B) << 6) | ns] ^= v;
                    if (!ns) break;
                }
                if (!st) break;
            }
        }
        else
        {
            ull ans = 0;
            uint D = C ^ 63;
            for (uint st = A; ; st = (st - 1) & A)
            {
                for (uint ns = D; ; ns = (ns - 1) & D)
                {
                    ans ^= vl[(st << 16) | (B << 6) | ns];
                    if (!ns) break;
                }
                if (!st) break;
            }
            bool res = 0;
            for (int i = 0; i < 64; i++)
                if ((x & i) == i) res ^= ((ans >> i) & 1);
            cout << res << "\n";
        }
    }
	return 0;
}