二叉交换树
题目描述
小 $D$ 最近对二叉树以及交换非常感兴趣，他想要把这两个东西合在一起，于是他得到了二叉交换树（Binary Swap Tree，简称 BST）。
二叉交换树是一棵高度为 $n+1$ 的满二叉树（即满足前 $n$ 层节点均有且仅由两个孩子，而第 $n+1$ 层节点都是叶节点的二叉树）。
一棵二叉交换树共有 $2^n$ 个叶子，从左到右依次写着 $L_1,L_2,L_3,\cdots,L_{2^n}$。它还有 $2^n-1$ 个非叶节点，我们用 $(i,j)$ 表示此时从上到下第 $i$ 层的第 $j$ 个节点，我们还可以用 $T_{2^{i-1}+j-1}$ 表示这个节点。
作为一棵二叉交换树，自然要支持交换操作。我们定义 $swap(u)$ 表示交换节点 $T_u$ 的左右子树（即原来的左子树变为右子树，而原来的右子树变为左子树）。
注意：在交换操作之后：
- 原来的 $T_x$ 和现在的 $T_x$ 可能并不是一个节点，这是因为 $(i,j)$ 表示的是当前树上处于这个位置的节点；
- 但是，$L_x$ 始终表示同一个叶子，这是因为 $L_x$ 是写在叶子上的，会和节点位置的变化而一同变化。
小 $D$ 现在进行了 $q$ 次操作，操作有两种：
1 L R表示依次进行 $swap(L),swap(L+1),swap(L+2),\cdots,swap(R)$ 的操作（注意在相邻两次操作之间，节点的重编号也会被进行）。2 x表示询问当前从左到右第 $x$ 个叶子上面写着什么。
然而小 $D$ 无法维护过于巨大的树，请你帮帮他。
输入格式
第一行两个空格隔开的整数 $n,q$，意义如题面所示。
接下来 $q$ 行，每行两个或三个整数，表示一次询问。其格式如题面所示。
输出格式
对于每一个操作 2，输出一行一个整数表示答案。如果这个叶子写着 $L_a$，则你只要输出 $a$ 即可。
样例输入 1
3 10 1 5 5 2 1 2 2 2 3 2 4 1 1 3 2 2 2 3 2 5 2 6
样例输出 1
1 2 4 3 8 5 4 3
样例解释 1
初始时，树的形态如图所示：
（见下发文件 pic1.png）
第一次交换操作是 $swap(5)$，即对上图中的红色节点进行了操作，得到：
（见下发文件 pic2.png）
接下来第二次交换操作先进行了 $swap(1)$，即上图中的红色节点，得到：
（见下发文件 pic3.png）
然后进行了 $swap(2)$，即上图中的红色节点，得到：
（见下发文件 pic4.png）
最后进行了 $swap(3)$，即上图中的红色节点，得到：
（见下发文件 pic5.png）
样例输入输出 2 & 3 & 4 & 5
见下发文件 ex_bst2.in/out、ex_bst3.in/out、ex_bst4.in/out 以及 ex_bst5.in/out。其中 ex_bst3.in 满足特殊性质一，而 ex_bst4.in 满足特殊性质二（见 “数据规模与约定” 一节）。
数据规模与约定
本题共 $20$ 个测试数据，每个测试数据 $5$ 分。
对于前 $10\%$ 的数据，$1\le n\le 3$，$1\le q\le 10$；
对于另 $20\%$ 的数据，$1\le n\le 10$，$1\le q\le 2000$；
对于另 $\ \ 5\%$ 的数据，$1\le n\le 17$，$1\le q\le 2\times 10^5$，且满足特殊性质一；
对于另 $10\%$ 的数据，$1\le n\le 17$，$1\le q\le 2\times 10^5$，且满足特殊性质二；
对于另 $25\%$ 的数据，$1\le n\le 17$，$1\le q\le 2\times 10^5$；
对于另 $\ \ 5\%$ 的数据，满足特殊性质一；
对于另 $10\%$ 的数据，满足特殊性质二；
对于 $100\%$ 的数据，有 $1\le n\le 20$，$1\le q\le 10^6$，$1\le L\le R\lt 2^n$，$1\le x\le 2^n$。
其中，特殊性质一表示：对于操作 1，存在整数 $k$ $(0\le k\lt n)$，使得 $L=2^k$ 且 $R=2^{k+1}-1$。而特殊性质二表示：对于操作 1，存在整数 $x,y$ $(0\le x\lt y\le n)$，使得 $L=2^x$ 且 $R=2^y-1$。
友情提醒：本题输入输出数据量可能很大，对于使用 C++ 语言的选手，如果使用 (std::)cin/cout 进行输入输出将会直接导致 $q$ 较大的部分测试点超时，请关闭流同步或改为使用 scanf/printf 才有可能得到这一部分的分数。
时间限制：$2\mathtt{s}$
空间限制：$512\mathtt{MB}$
