#include <bits/stdc++.h>
#define mm 2048
#define ui unsigned int
#define ULL unsigned long long
static char buf[1000000],*paa=buf,*pd=buf;
static char buf2[1000000],*pp=buf2;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline void pc(char ch){
	if(pp-buf2==1000000) fwrite(buf2,1,1000000,stdout),pp=buf2;
	*pp++=ch;
}
inline void pcc(){
	fwrite(buf2,1,pp-buf2,stdout);
	pp=buf2;
}
inline ui read(void){
	register ui x(0);register char c(getchar());
	while(c<'0'||c>'9'){c=getchar();}
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}
ULL vq[(1<<11)+2][(1<<15)+2],sm[(1<<11)+2],la[(1<<15)+2];
int N,Q,sz;ui tp[1000009],num[1000009];
bool fl[1000009];
signed main(void) {
	N=read();Q=read();
	std::mt19937 rng(6666);
	for(int i=1;i<=Q;i++) {
		char op=getchar();
		while(op!='?'&&op!='!') op=getchar();
		if(op=='!') fl[i]=1;
		num[i]=read();
	}
	int p[35],ph[35];
	for(int i=0;i<N;i++) p[i]=i;
	for(int i=1;i<N;i++) {
		std::swap(p[i],p[rng()%i+1]);
	}
/*	for(int i=1;i<=Q;i++) {
		ui as=0;
		for(int j=0;j<N;j++) {
			if((num[i]>>j)&1) as|=(1ull<<p[j]);
		}	
		num[i]=as;	
	}*/
	int cnt=0;
	long long laa=0;
	for(int rt=0;rt<N;rt+=4) {
		long long ans=0;int sq=0;
		for(int i=1;i<=Q;i++) {
			if(!fl[i]) {
				ui as=(num[i]>>rt)|((num[i]&((1ull<<rt)-1))<<(N-rt));
				ui xx=(as-(as&63))/64/mm;
				if(xx<(1<<N-6)/mm-1) ans+=std::min((1<<__builtin_popcount(xx)),sq/4);
			} else {
				sq++;
				ui as=(num[i]>>rt)|((num[i]&((1ull<<rt)-1))<<(N-rt));				
				ui a1=(as&(mm-1)),a2=(as-a1)/mm;
				ui a3=mm-1-a1;
				if(a3<mm-1) ans+=(1<<__builtin_popcount(a3))*4;
			}
		}
		if(ans<laa||rt==0) {
			laa=ans;
			for(int i=1;i<=Q;i++) num[i]=(num[i]>>rt)|((num[i]&((1ull<<rt)-1))<<(N-rt));
//				ph[i]=p[i];
		}
	}
	for(int ix=1;ix<=Q;ix++) {
		cnt++;
		ui x=num[ix];
//		x=y;
		if(!fl[ix]) {
			int ff=0;
			ui xx=(x-(x&63))/64/mm;
			if(xx<(1<<N-6)/mm-1&&(1<<__builtin_popcount(xx))>6*sz) {
				int la=0;
				for(int i=0;i+7<sz;i+=8) {
					if((x&tp[i])==tp[i]) ff^=1;
					if((x&tp[i+1])==tp[i+1]) ff^=1;
					if((x&tp[i+2])==tp[i+2]) ff^=1;
					if((x&tp[i+3])==tp[i+3]) ff^=1;
					if((x&tp[i+4])==tp[i+4]) ff^=1;
					if((x&tp[i+5])==tp[i+5]) ff^=1;
					if((x&tp[i+6])==tp[i+6]) ff^=1;
					if((x&tp[i+7])==tp[i+7]) ff^=1;
					la=i+8;
				}
				for(int i=la;i<sz;i++) {
					if((x&tp[i])==tp[i]) ff^=1;
				}
			} else {
				int tp=(x&63);
				x-=tp;x/=64;
				ui a1=(x&(mm-1)),a2=(x-a1)/mm;
				ULL aq=0,tt=0;
				for(int i=0;i<64;i++) if((tp&i)==i) aq|=(1ull<<i);
				if(a2==(1<<N-6)/mm-1) {
					tt=sm[a1];
				} else {
					tt^=vq[a1][0];
					if(a2) {
						for(ui i=a2;i;i=a2&(i-1)) tt^=vq[a1][i];
					}
					ui a3=(a2&255);a2-=a3;
					tt^=la[a3];
					if(a2) for(ui i=a2;i;i=a2&(i-1)) tt^=la[i|a3];
				}
				tt&=aq;
				ff=__builtin_popcountll(tt)&1;
//				for(int i=0;i<64;i++) if((tt>>i)&1) ff^=1;
			}
			pc(ff+'0');pc('\n');
		} else {
			tp[sz++]=x;
			ULL tt=(1ull<<(x&63));
			x>>=6;
			ui a1=(x&(mm-1)),a2=(x-a1)/mm;
			ui a3=mm-1-a1;
			sm[a1]^=tt;
			if(a3) for(ui i=a3;i;i=a3&(i-1)) sm[a1+i]^=tt;
			if(a1==0) {
				ui a4=255-(a2&255);
				la[a2]^=tt;
				for(ui i=a4;i;i=a4&(i-1)) la[a2+i]^=tt;
			} else {
				vq[a1][a2]^=tt;
				if(a3) for(ui i=a3;i;i=a3&(i-1)) vq[a1+i][a2]^=tt;
			}
		}
		/*if(Q%1000==0&&(clock()>CLOCKS_PER_SEC*4.98)) {
			pcc();
			return 0;
		}*/
	}
	std::cerr<<(long double)clock()/CLOCKS_PER_SEC<<"seconds"<<std::endl;
	pcc();
}