#include<bits/stdc++.h>
#define ui unsigned int
#define ull unsigned long long
using namespace std;
namespace IO {
int ow,olim=(1<<23)-100;
char buf[1<<21],*p1=buf,*p2=buf,obuf[1<<23];
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ui read() {
	ui x=0; char c=gc();
	while(!isdigit(c)) c=gc();
	while(isdigit(c)) x=x*10+(c^48),c=gc();
	return x;
}
char getc() {
	char c=gc();
	while(c!='!'&&c!='?') c=gc();
	return c;
}
void flush() {
	fwrite(obuf,ow,1,stdout),ow=0;
}
void putc(char c) {
	obuf[ow++]=c;
	if(ow>=olim) flush();
}
#undef gc
}
ull f0[256][15628],f1[256][15628],f2[256][15628],f3[256][15628];
signed main() {
	int N=IO::read(),q=IO::read(),n=0,k=0;
	while(q--) {
		char op=IO::getc();
		ui x=IO::read();
		ui a=x&255,b=x>>8&255,c=x>>16&255,d=x>>24&255,t;
		if(op=='!') {
			ull z=1ull<<(n&63);
			for(t=a;t<256;t=(t+1)|a) f0[t][k]^=z;
			for(t=b;t<256;t=(t+1)|b) f1[t][k]^=z;
			for(t=c;t<256;t=(t+1)|c) f2[t][k]^=z;
			for(t=d;t<256;t=(t+1)|d) f3[t][k]^=z;
			++n,k=n>>6;
		} else {
			ull s=0,*g0=f0[a],*g1=f1[b],*g2=f2[c],*g3=f3[d];
			for(t=0;t<=k;++t) s^=g0[t]&g1[t]&g2[t]&g3[t];
			IO::putc('0'+__builtin_parityll(s)),IO::putc('\n');
		}
	}
	IO::flush();
	return 0;
}