#include <bits/stdc++.h>
#define ui unsigned
#define ull ui long long
using namespace std;
#define USE_FREAD_FWRITE
#define READ_NEGATIVE
#define WRITE_NEGATIVE
#define DEFAULT_TYPE int
namespace IO{
#ifdef USE_FREAD_FWRITE
#define SIZE (1<<20)
	char in[SIZE],out[SIZE],*p1=in,*p2=in,*p3=out;
	char getchar(){ return p1==p2&&(p2=(p1=in)+fread(in,1,SIZE,stdin),p1==p2)?EOF:*p1++; }
	void flush(){ int len=p3-out; fwrite(p3=out,1,len,stdout); }
	void putchar(char ch){ if(p3==out+SIZE)flush(); *p3++=(ch); }
	struct Flush{~Flush(){flush();}}_;
#else
	char getchar(){ return ::getchar(); }
	void putchar(char ch){ ::putchar(ch); }
	void flush(){}
#endif
	template<typename type=DEFAULT_TYPE> inline type read(){
#ifdef READ_NEGATIVE
		type x(0);bool flag(0);char ch=getchar();
		for(;ch<'0'||ch>'9';ch=getchar())flag^=ch=='-';
		for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
		return flag?-x:x;
#else
		type x(0);char ch=getchar();
		for(;ch<'0'||ch>'9';ch=getchar());
		for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
		return x;
#endif
	}
	template<typename type>
	inline void write(type x){
#ifdef WRITE_NEGATIVE
		if(x<0)x=-x,putchar('-');
#endif
		static int Stack[50],top(0);
		do Stack[++top]=x%10,x/=10;while(x);
		while(top) putchar(Stack[top--]|48);
	}
}
using IO::read;
using IO::write;
const int N=1e6+10;
mt19937 rnd(0);
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int n,m;
ui op[N],at[N];
char conf[32];
void get_conf(){
	static char tmp[32];
	long long tc=1e18,tt=0;
	while(tc>=1e9){
		ui sa=0,sb=0,sc=0;
		for(int i=6;i<32;i++){
			tmp[i]="abc"[rnd()%3];
			if(tmp[i]=='a') sa|=(1u<<i);
			if(tmp[i]=='b') sb|=(1u<<i);
			if(tmp[i]=='c') sc|=(1u<<i);
		}
		tt=0;
		for(int i=1;i<=m;i++){
			tt+=1u<<__builtin_popcount(op[i]?(~at[i])&sc|at[i]&sa:(~at[i])&sb|at[i]&sc);
		}
		if(tt<=tc){
			// fprintf(stderr,"%s %lld\n",tmp+6,tt);
			tc=tt;
			memcpy(conf,tmp,sizeof(conf));
		}
	}
	// cerr<<"TC: "<<tc<<endl;
}
ull a[1<<26];
void change(ui x){
	ui y=x&63;
	ull s=0;
	for(int i=63;i>=0;i--) s=(s<<1)|((i&y)==y);
	ui z=0;
	for(int i=6;i<32;i++){
		if(conf[i]=="bc"[x>>i&1]){
			z|=(1u<<i);
		}
	}
	x>>=6; z>>=6;
	for(ui i=z;;i=(i-1)&z){
		// printf("c %d\n",x^i);
		a[x^i]^=s;
		if(!i) break;
	}
}
bool query(ui x){
	ui y=x&63;
	ui z=0;
	for(int i=6;i<32;i++){
		if(conf[i]=="ca"[x>>i&1]){
			z|=(1u<<i);
		}
		if(conf[i]=='c'){
			x^=(1u<<i);
		}
	}
	x>>=6; z>>=6;
	ull ans=0;
	for(ui i=z;;i=(i-1)&z){
		// printf("q %d\n",x^i);
		ans^=a[x^i];
		if(!i) break;
	}
	return (ans>>y)&1;
}
int main(){
	n=read(); m=read();
	for(int i=1;i<=m;i++){
		char o; do o=IO::getchar(); while(o!='!'&&o!='?');
		const ui x=read();
		op[i]=(o=='?'); at[i]=x;
	}
	get_conf();
	for(int i=1;i<=m;i++){
		if(op[i]){
			IO::putchar('0'+query(at[i])); IO::putchar('\n');
		}else{
			change(at[i]);
		}
	}
}