「EZEC-7」维护序列

[](https://www.luogu.com.cn/paste/tdqr0sto) 可怜的 dead_X 收不了歌，于是他出了个水题并给参赛者送了 $100$ 分。 2022 Update: 已经收了，很水。

你需要维护一个序列。 这个序列开始时有 $2^n$ 个数，下标从 $0$ 开始。第 $i$ 个数初始值为 $i$，需要支持以下三种操作： * 定义 $a$ 为所有下标为偶数的数组成的子序列，$b$ 为所有下标为奇数的数组成的子序列，将 $a,b$ 连接，构成新的序列。 * 定义 $a$ 为所有下标为奇数的数组成的子序列，$b$ 为所有下标为偶数的数组成的子序列，将 $a,b$ 连接，构成新的序列。 * 查询下标为 $x$ 的数。 总共将进行 $m$ 次操作。

第一行输入两个正整数 $n,m$。 接下来输入 $m$ 行，每行输入两个非负整数 $op,x$，代表一次操作。 如果 $op=1$，若 $x=0$，代表第一种操作，若 $x=1$，代表第二种操作。 如果 $op=2$，代表第三种操作，参数 $x$ 即为输入的 $x$。

对于每个 $op=2$ 输出一行，即对应的数。

2 7
2 0
1 0
2 1
1 1
2 2
1 0
2 3

0
2
0
1

**【样例解释】** 所有操作前后的序列从左至右的数如下： $$\{0,1,2,3\}$$ 下标为 $0$ 的数为 $0$。 $$\{0,2\},\{1,3\}$$ $$\{0,2,1,3\}$$ 下标为 $1$ 的数为 $2$。 $$\{2,3\},\{0,1\}$$ $$\{2,3,0,1\}$$ 下标为 $2$ 的数为 $0$。 $$\{2,0\},\{3,1\}$$ $$\{2,0,3,1\}$$ 下标为 $3$ 的数为 $1$。 **【数据范围】** **本题采用捆绑测试。** - Subtask 1（10 points）：不存在 $op=1$ 的操作。 - Subtask 2（10 points）：$n\leq 10，m\leq 10^3$。 - Subtask 3（20 points）：$n\leq 10$。 - Subtask 4（20 points）：$m\leq 10^3$。 - Subtask 5（20 points）：对于 $op=1$ 的操作，$x=0$。 - Subtask 6（20 points）：无特殊限制。 对于 $100\%$ 的数据，$1\leq n\leq 32$，$1\leq m\leq 10^6$。 若 $op=1$，$x\in\{0,1\}$，若 $op=2$，$0\leq x<2^n$。