题目背景

バグ。

迷子　迷子　真っ只中　さあ　パ　パ　パ　ラ　パーラノーイ「ア」

ギコギコ　MY HEART(マイココロ)剪定 　パ　パ　パ　ラ　パーラノーイ「ア」

题目描述

雪有一棵 $n$ 层的满二叉树。按二叉树层次遍历（见解释）编号。

这棵树经历了 $m$ 次操作。

1. 这棵树发生了故障。把 $u$ 点与父节点的边删除。如果节点是根节点或者这条边已经被删掉则什么也不做。

2. 询问 $u$ 点的连通块大小。

“身为迷失的孩子，即使那么不情愿，也还是需要那份爱吗？”

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行每行两个整数 $o,u$。

如果 $o=1$ 则对 $u$ 进行 $1$ 操作，如果 $o=2$ 则对 $u$ 进行 $2$ 操作。

输出格式

为了简化输出量，你只需要输出一行，表示对于每次询问时所有答案的异或和。

5 3
2 3
1 3
2 3

16

5 3
1 2
1 3
2 1

1

提示

二叉树及相关问题

1. $n$ 层的满二叉树指的是最大深度为 $n$ 的满二叉树，其中根节点的深度为 $1$。
2. 根节点的编号为 $1$。如果 $i$ 点存在儿子，满二叉树的层次遍历编号满足 $i$ 的左儿子编号是 $2i$，右儿子编号是 $2i+1$。

样例解释 1

对于第一次询问，删去 $3$ 到 $1$ 的边之前答案为整棵树的大小 $31$，删去后变为了 $3$ 的子树大小 $15$。异或和为 $31\oplus 15=16$。

数据范围

共 $10$ 个数据点，不开启捆绑测试。

对于前 $20\%$ 的数据，$n \leq 10,m \leq 10^3$。

对于前 $50\%$ 的数据，$n \leq 20,m \leq 10^4$。

对于前 $80\%$ 的数据，$n\le 30$。

对于所有数据，$2\le n \leq 60,1\le m \leq 3\times 10^5,1\le o\le 2,1\le u\le 2^n -1$。