#1055. 1-06H. nocriz与'Swappy Tree'

nocriz是一个好学的同学。

nocriz同学了解到有一种叫Swappy Tree的神奇的树。

Swappy Tree 是一棵高度为 $n + 1$，有着 $2^n$ 个叶子的完全二叉树。叶子从左向右分别写着为 $1, 2, \dots, 2^n$。 对于非叶子节点，在所有时刻，我们将从上往下第 $i$ 层，从左往右第 $j$ 个的点称为 $2^{i - 1} + j - 1$。 这里，我们定义 swap(x) 为交换 $x$ 号节点的左右子树（交换后第 $i$ 个非叶子节点依然按上文中的方法定义）。 Swappy Tree上要进行以下两种操作：

• 给定 $k$ $(k\leq 2^n)$，求出从左往右第k个叶子上的值。

• 给定 $a, b$ $(1 \le a \le b \le 2^n - 1)$，依次进行 swap(a)$,$ swap(a+1)$, \dots,$ swap(b)。

你需要代替nocriz同学实现一棵Swappy Tree。 具体来说，给定 $n$ 和 $q$ 个询问，请对其处理并做出一棵Swappy Tree。

第一行包含两个整数 $n, q$。

接下来 $q$ 行，每行包括三个整数$t_i,a_i,b_i$，表示一组操作。

若 $t_i = 1$，$a_i$即为询问中的$k$，保证$b_i=0$。

若 $t_i = 2$，$a_i$ 与 $b_i$ 即为修改中的 $a$ 与 $b$。

对于每一个询问，在新的一行中输出答案。

输入样例

3 10
2 5 5
1 1 0
1 2 0
1 3 0
1 4 0
2 1 3
1 2 0
1 3 0
1 5 0
1 6 0

输出样例

1
2
4
3
8
5
4
3

$1 \le n \le 17$

$1 \le q \le 2 \cdot 10^5$