题目背景

可怜的 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$。