二叉交换树
题目描述
小 D 最近对二叉树以及交换非常感兴趣，他想要把这两个东西合在一起，于是他得到了二叉交换树（Binary Swap Tree，简称 BST）。
二叉交换树是一棵高度为 n+1 的满二叉树（即满足前 n 层节点均有且仅由两个孩子，而第 n+1 层节点都是叶节点的二叉树）。
一棵二叉交换树共有 2n 个叶子，从左到右依次写着 L1,L2,L3,⋯,L2n。它还有 2n−1 个非叶节点，我们用 (i,j) 表示此时从上到下第 i 层的第 j 个节点，我们还可以用 T2i−1+j−1 表示这个节点。
作为一棵二叉交换树，自然要支持交换操作。我们定义 swap(u) 表示交换节点 Tu 的左右子树（即原来的左子树变为右子树，而原来的右子树变为左子树）。
注意：在交换操作之后：
- 原来的 Tx 和现在的 Tx 可能并不是一个节点，这是因为 (i,j) 表示的是当前树上处于这个位置的节点；
- 但是，Lx 始终表示同一个叶子，这是因为 Lx 是写在叶子上的，会和节点位置的变化而一同变化。
小 D 现在进行了 q 次操作，操作有两种：
1 L R表示依次进行 swap(L),swap(L+1),swap(L+2),⋯,swap(R) 的操作（注意在相邻两次操作之间，节点的重编号也会被进行）。2 x表示询问当前从左到右第 x 个叶子上面写着什么。
然而小 D 无法维护过于巨大的树，请你帮帮他。
输入格式
第一行两个空格隔开的整数 n,q，意义如题面所示。
接下来 q 行，每行两个或三个整数，表示一次询问。其格式如题面所示。
输出格式
对于每一个操作 2，输出一行一个整数表示答案。如果这个叶子写着 La，则你只要输出 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≤n≤3，1≤q≤10；
对于另 20% 的数据，1≤n≤10，1≤q≤2000；
对于另 5% 的数据，1≤n≤17，1≤q≤2×105，且满足特殊性质一；
对于另 10% 的数据，1≤n≤17，1≤q≤2×105，且满足特殊性质二；
对于另 25% 的数据，1≤n≤17，1≤q≤2×105；
对于另 5% 的数据，满足特殊性质一；
对于另 10% 的数据，满足特殊性质二；
对于 100% 的数据，有 1≤n≤20，1≤q≤106，1≤L≤R<2n，1≤x≤2n。
其中，特殊性质一表示：对于操作 1，存在整数 k (0≤k<n)，使得 L=2k 且 R=2k+1−1。而特殊性质二表示：对于操作 1，存在整数 x,y (0≤x<y≤n)，使得 L=2x 且 R=2y−1。
友情提醒：本题输入输出数据量可能很大，对于使用 C++ 语言的选手，如果使用 (std::)cin/cout 进行输入输出将会直接导致 q 较大的部分测试点超时，请关闭流同步或改为使用 scanf/printf 才有可能得到这一部分的分数。
时间限制：2s
空间限制：512MB
