// created:  2024-10-22 08:55:24
#include<cstdio>
#include<cctype>
#include<algorithm>
#define F(i,l,r) for(int i=(l),i##_end=(r);i<i##_end;++i)
#define I128 //||is_same<T,__int128_t>::value||is_same<T,__uint128_t>::value
using namespace std;
template<typename T>enable_if_t<is_integral<T>::value I128,void> readmain(T &x)
{
	bool neg=false;int c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')neg=true;
	for(x=0;isdigit(c);c=getchar())x=(T)(10*x+(c-'0'));
	if(neg)x=-x;
}
template<typename T>T& read(T &x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &x,Tr&... r){readmain(x);read(r...);}
typedef unsigned uint;
typedef unsigned long long ull;
struct bitset
{
	static constexpr int N=15700;
	ull a[N];
}a[4][(1<<8)+5];
int n,h[4],q,m;
int main()
{
	read(n,q);
	F(i,0,4)h[i]=(n+3-i)/4;
	while(q--)
	{
		char opt;scanf(" %c",&opt);
		uint x;read(x);
		if(opt=='!')
		{
			int m1=m>>6;ull m2=1ull<<(m&63);
			F(i,0,4)
			{
				int y=x&((1<<h[i])-1),f=((1<<h[i])-1)^y;x>>=h[i];
				for(int r=f;r;--r&=f)a[i][y+r].a[m1]|=m2;
				a[i][y].a[m1]|=m2;
			}
			++m;
		}
		else
		{
			bitset *b[4];
			F(i,0,4)b[i]=&a[i][x&((1<<h[i])-1)],x>>=h[i];
			ull ans=0;
			F(i,0,(m+63)>>6)ans^=b[0]->a[i]&b[1]->a[i]&b[2]->a[i]&b[3]->a[i];
			printf("%d\n",__builtin_parityll(ans));
		}
	}
	return 0;
}