#include<iostream>
#include<cstdio>
#include<bitset>
#define N 100
#define M 16384
using namespace std;
unsigned int read()
{
	char c=0;
	unsigned int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int n,q,sz;
bool res;
unsigned long long B[1<<12][M+1],delta[1<<10][M+1],delta2[1<<10][M+1];
int main()
{
	char op;
	int s1,s2,d1,d2,w;
	unsigned int x;
	unsigned long long dw;
	for (int i=0;i<(1<<10);++i)
		for (int j=0;j<(1<<10);++j)
			if ((j&i)==j)
			{
				for (int k=0;k<(1<<10);++k) w=j|(k<<10),delta[i][w>>6]|=(1ull<<(w&63));
			}
	for (int i=0;i<(1<<10);++i)
		for (int j=0;j<(1<<10);++j)
			if ((j&i)==j)
			{
				for (int k=0;k<(1<<10);++k) w=k|(j<<10),delta2[i][w>>6]|=(1ull<<(w&63));
			}
	n=read(),q=read(),sz=1<<max(n-18,0);
	for (int i=1;i<=q;++i)
	{
		cin>>op,x=read();
		if (op=='!')
		{
			s1=x&((1<<12)-1),s2=x>>12,d1=s2>>6,d2=s2&63,dw=1ull<<d2;
			for (int j=s1;j<(1<<12);j=(j+1)|s1) B[j][d1]^=dw;
		}
		else
		{
			s1=x&((1<<12)-1),s2=x>>12,d1=s2&((1<<10)-1),d2=s2>>10,res=0;
			for (int j=0;j<sz;++j) res^=__builtin_parityll(B[s1][j]&delta[d1][j]&delta2[d2][j]);
			printf("%d\n",res);
		}
	}
	return 0;
}