「EZEC-7」维护序列

题目背景

[![](https://cdn.luogu.com.cn/upload/image_hosting/lo9tuyl9.png)](https://www.luogu.com.cn/paste/tdqr0sto) 可怜的 dead_X 收不了歌,于是他出了个水题并给参赛者送了 $100$ 分。

题目描述

你需要维护一个序列。 这个序列开始时有 $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$ 输出一行,即对应的数。

输入输出样例

输入样例 #1

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

输出样例 #1

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$。