#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
unordered_map<int, int> flag1, flag2;
// flag1 -> 边是否被删除 flag2->子树减少的数量
int getsize(int i)
{
	return (1 << (int)(n-floor(log2(i))))-1;
}
int getfather(int i) 
{
	if (i % 2 == 0)
		return i/2;
	else return (i-1)/2;
}
int getroot(int i)
{
	if (flag1[i] == 1)
		return i;
	if (i == 1)
		return 1;
	else return getroot(getfather(i));
}
int solve(int i)
{
	int rt = getroot(i);
	return getsize(rt)-flag2[rt];
}
void del(int u)
{
	if (u == 1)
		return ;
	int sz = getsize(u)-flag2[u];
	int pos = u;
	while (flag1[pos] == 0 && pos != 1)
	{
		pos = getfather(pos);
		flag2[pos] += sz;
	}
	flag1[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;
}

这个能得60 pts 会TLE，听说要用tire，怎么加进去？