// 0: 枚举询问的子集
// 1: 枚举修改的超集
// 2: 枚举询问补集的子集和修改的子集
#include <bits/stdc++.h>
using namespace std;
typedef unsigned u32;
typedef unsigned long long u64;
mt19937 eng(363415);
int n, u, q;
struct Oper {
	bool op; u32 x;	
} a[1000005];
int typ[26], tmp[26], pos0, pos1, pos2;
u64 minW = -1, f[67200000];
int main() {
	scanf("%d%d", &n, &q), u = n - 6;
	for (int i = 1; i <= q; i++) {
		char op; u32 x; scanf(" %c%u", &op, &x);
		a[i] = { op == '?', x };
	}
	for (int T = 1; T <= 10; T++) {
		for (int i = 0; i < u; i++) tmp[i] = eng() % 3;
		u64 s = 0;
		for (int i = 1; i <= q; i++) {
			u32 x = a[i].x >> 6; u64 t = 1;
			for (int j = 0; j < u; j++) {
				if (a[i].op) {
					if ((x >> j & 1) && tmp[j] == 0) t <<= 1;
					if (!(x >> j & 1) && tmp[j] == 2) t <<= 1;
				}
				else {
					if (!(x >> j & 1) && tmp[j] == 1) t <<= 1;
					if ((x >> j & 1) && tmp[j] == 2) t <<= 1;
				}
			}
			s += t;
		}
		if (s < minW) {
			minW = s;
			memcpy(typ, tmp, sizeof(typ));
		}
	}
	for (int i = 0; i < u; i++) typ[i] = 0;
	for (int i = 0; i < u; i++) {
		if (typ[i] == 0) pos0 |= 1 << i;
		else if (typ[i] == 1) pos1 |= 1 << i;
		else pos2 |= 1 << i;
	}
	for (int id = 1; id <= q; id++) {
		u32 x = a[id].x >> 6, y = a[id].x & 63;
		if (a[id].op) {
			u64 res = 0;
			u32 a = (x & pos0) | (~x & pos2), b = (x & pos1);
			for (u32 s = a; s; s = (s - 1) & a) {
				res ^= f[s | b];
			}
			res ^= f[b];
			int ans = 0;
			for (u32 s = 0; s < 64; s++) {
				if ((y & s) == s) ans ^= (res >> s & 1);
			}
			putchar('0' ^ ans), putchar('\n');
		}
		else {
			u32 a = x & pos2, b = (x & pos1) | ~pos1, c = x & pos0;
			for (u32 s = a; s; s = (s - 1) & a) {
				for (u32 t = b; t < (1 << u) - 1; t = (t + 1) | b) {
					f[s | (t & pos1) | c] ^= 1ull << y;
				}
				f[s | pos1 | c] ^= 1ull << y;
			}
			for (u32 t = b; t < (1 << u) - 1; t = (t + 1) | b) {
				f[(t & pos1) | c] ^= 1ull << y;
			}
			f[pos1 | c] ^= 1ull << y;
		}
	}
	return 0;
}