#include<bits/stdc++.h>
using namespace std;
using u32=unsigned;
using u64=unsigned long long;
mt19937 g(time(0));
int qn;
struct Q_{char op;u32 x;}q[1000010];
u64 a[1<<26],mcost=-1ull;
array<u32,3>S;
int main(){
   scanf("%*d%d",&qn);
   for(int i=1;i<=qn;i++){
      scanf(" %c%u",&q[i].op,&q[i].x);
   }
   for(int T=20;T--;){
      array<u32,3>s;u64 cost=0;
      for(int k=0;k<26;k++)s[g()%3]|=1<<k;
      for(int i=1;i<=qn;i++){
         u64 x=q[i].x>>6;
         cost+=1ull<<__builtin_popcount(q[i].op=='!'?(~x&s[0])|(x&s[2]):(x&s[1])|(~x&s[2]));
      }
      if(cost<mcost)mcost=cost,S=s;
   }
   u64 subs[64]{};
   for(int s=0;s<64;s++)for(int t=0;t<64;t++)
   if((s|t)==s)subs[s]|=1ull<<t;
   for(int i=1;i<=qn;i++){
      u32 u=q[i].x>>6,d=q[i].x&63;
      if(q[i].op=='!'){
         u32 U=(~u&S[0])|(u&S[2]);u&=~S[2];
         for(u32 w=U;;w=w-1&U){
            a[w^u]^=1ull<<d;
            if(!w)break;
         }
      }else{
         u32 U=(u&S[1])|(~u&S[2]);u&=~S[2];
         int ans=0;
         for(u32 w=U;;w=w-1&U){
            ans^=__builtin_parityll(a[w^u]&subs[d]);
            if(!w)break;
         }printf("%d\n",ans);
      }
   }
   return 0;
}