#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1000003;
struct Pair
{
	int first, second;
};
class Hash_table 
{
public:
	vector<Pair> table[mod+1];
	int getval(int x)
	{
		int index = x%mod, sz = table[index].size();
		for (int i=0;i<sz;i+=5)
		{
			if (table[index][i].first == x)
				return table[index][i].second;
			if (i+1 < sz && table[index][i+1].first == x)
				return table[index][i+1].second;
			if (i+2 < sz && table[index][i+2].first == x)
				return table[index][i+2].second;
			if (i+3 < sz && table[index][i+3].first == x)
				return table[index][i+3].second;
			if (i+4 < sz && table[index][i+4].first == x)
				return table[index][i+4].second;
		}
		return 0;
	}
	void insert(int x, int y)
	{
		int index = x%mod;
		for (int i=0;i<table[index].size();i+=5)
		{
			if (table[index][i].first == x)
			{
				table[index][i].second = y;
				return ;
			}
			if (table[index][i+1].first == x)
			{
				table[index][i+1].second = y;
				return ;
			}
			if (table[index][i+2].first == x)
			{
				table[index][i+2].second = y;
				return ;
			}
			if (table[index][i+3].first == x)
			{
				table[index][i+3].second = y;
				return ;
			}
			if (table[index][i+4].first == x)
			{
				table[index][i+4].second = y;
				return ;
			}
		}
		table[index].push_back(Pair{x, y});
	}
};
int n, m;
Hash_table flag1, flag2;
// flag1 -> 边是否被删除 flag2->子树减少的数量
inline int getsize(int i)
{
	return (1LL << (int)(n-floor(log2(i))))-1;
}
inline int getfather(int i)
{
	if (i % 2 == 0)
		return i/2;
	else return (i-1)/2;
}
int getroot(int i)
{
	if (flag1.getval(i) == 1)
		return i;
	if (i == 1)
		return 1;
	else return getroot(getfather(i));
}
inline int solve(int i)
{
	int rt = getroot(i);
	return getsize(rt)-flag2.getval(rt);
}
void del(int u)
{
	if (u == 1)
		return ;
	int sz = getsize(u)-flag2.getval(u);
	int pos = u;
	while (flag1.getval(pos) == 0 && pos != 1)
	{
		pos = getfather(pos);
		flag2.insert(pos, flag2.getval(pos)+sz);
	}
	flag1.insert(u, 1);
	return ;
}
inline int read()
{
	int x = 0, f = 1;
	char c = getchar();
	while (c > '9' || c < '0')
	{
		if (c == '-')
			c = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9')
	{
		x = (x << 3)+(x << 1)+c-48;
		c = getchar();
	}
	return x*f;
}
signed main()
{
	n = read();
	m = read();
	int ans = 0;
	while (m--)
	{
		int op, u;
		op = read();
		u = read();
		if (op == 1)
		{
			del(u);
		}
		else 
		{
			ans ^= solve(u);
		}
	}
	cout << ans;
	return 0;
}

#9 实在过不去