#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[15628][1<<8],f1[15628][1<<8],f2[15628][1<<8],f3[15628][1<<8];
signed main() {
	int N=IO::read(),q=IO::read(),n=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;
		if(op=='!') {
			ull z=1ull<<(n&63);
			for(ui t=a;t<256;t=(t+1)|a) f0[n>>6][t]^=z;
			for(ui t=b;t<256;t=(t+1)|b) f1[n>>6][t]^=z;
			for(ui t=c;t<256;t=(t+1)|c) f2[n>>6][t]^=z;
			for(ui t=d;t<256;t=(t+1)|d) f3[n>>6][t]^=z;
			++n;
		} else {
			ull s=0;
			for(int i=0;i<=(n>>6);++i) s^=f0[i][a]&f1[i][b]&f2[i][c]&f3[i][d];
			IO::putc('0'+__builtin_parityll(s)),IO::putc('\n');
		}
	}
	IO::flush();
	return 0;
}