#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 uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

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

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

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
namespace io {
	const int __SIZE = (1 << 22) + 1;
	char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
	#define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
	inline void gc (char &x) { x = Gc(); }
	inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
	inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
	inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';)  __c = Gc();
		for(; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc()) *s = __c; *s = 0; }
	template <class I> inline bool read (I &x) { _eof = 0;
		for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
		for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
	template <class I> inline void write (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10; while (qr) pc (qu[qr --]); }
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
} using io::pc; using io::gc; using io::pstr; using io::gstr; using io::read; using io::write;

int n,q;
ull a[1 << 26],b[1 << 26],c[1 << 26];
char str[5];

const int lim = 6,bas = (1u << lim) - 1;
int frp(int S){
	return (1 << (n - lim)) - 1 - S;
}
void ins(int S,ull val){
	c[S] ^= val;
	if(popcnt(S) <= (n - lim) / 2){
		for(int T = S;T;T = (T - 1) & S) a[T] ^= val;
		a[0] ^= val;		
	}else{
		S = frp(S);
		for(int T = S;T;T = (T - 1) & S) b[T] ^= val;
		b[0] ^= val;
	}
//	printf("ins %d %llu\n",S,val);
}

ull qry(int S){
	ull ret = b[frp(S)];
//	printf("qry %d\n",S);
	if(popcnt(S) <= (n - lim) / 2){
		ret = c[0];
		for(int T = S;T;T = (T - 1) & S) ret ^= c[T];
		return ret;
	}
	S = frp(S);
	ret ^= a[0];
	for(int T = S;T;T = (T - 1) & S) ret ^= a[T];
	return ret;
}

int main(){
//	freopen("ex_subset100.in","r",stdin);
//	freopen("test.out","w",stdout);
	read(n);read(q);
	uint val;
	ull msk;
	int tle = 0;
	rep(i,1,q){
		gstr(str + 1);
		read(val);
		if(i % 100 == 0 && (double)clock()/CLOCKS_PER_SEC>4.95) tle = 1;
		if(tle){
			if(str[1] != '!') pstr("0\n");
			continue;
		}
		if(str[1] == '!'){
			msk = 0;
			rep(S,0,(1 << lim) - 1) if((val & S) == (val & bas)) msk |= 1llu << S;
			ins(val >> lim,msk);
		}else{
			msk = qry(val >> lim);
			val &= bas;
			if((msk >> val) & 1) pstr("1\n");
			else pstr("0\n");
		}
	}
	cerr << clock() << "\n";
	return 0;
}