AT_arc049_d.[ARC049D] すわっぷしまーす

高桥君在旅行中参观了一棵奇特的完全二叉树，名为「すわっぷしまーす」。

这棵完全二叉树的高度是 $N+1$，具有 $2^N$ 个叶子节点。每个叶子节点从左到右依次标记为 $1, 2, 3, \ldots, 2^N$。

对于非叶子节点，位置的定义如下：位于第 $i$ 层（$1 \le i \le N$）且从左边数第 $j$ 个节点（$1 \le j \le 2^{i-1}$）的位置是 $2^{i-1} + (j-1)$。

此外，定义操作 ${\rm swap}(x)$，意为找到位置为 $x$ 的节点，并交换其左右子树。

「すわっぷしまーす」可以处理两类查询：

类型 1: 给予 $k(1 \le k \le 2^N)$，求第 $k$ 个叶子节点上的数字。

类型 2: 给出 $a, b(1 \le a \le b \le 2^N - 1)$，按顺序执行 ${\rm swap}(a), {\rm swap}(a+1), \ldots, {\rm swap}(b)$。

高桥君希望能够构建一个自己的「すわっぷしまーす」，但是遇到了困难。因此，请你帮助他实现这一目标。具体任务是：给定 $N$ 和 $Q$ 个查询，你需要构建并维护一棵能够处理这些查询的「すわっぷしまーす」。

从标准输入中读取数据，格式如下：

$N$ $Q$ $t_1$ $a_1$ $b_1$ $t_2$ $a_2$ $b_2$ \ldots $t_Q$ $a_Q$ $b_Q$

• 第一行包含两个整数 $N(1 \le N \le 17)$ 和 $Q(1 \le Q \le 200,000)$。
• 接下来的 $Q$ 行，每行包含三个整数 $t_i$, $a_i$, $b_i$。
  • 若 $t_i = 1$，这是一类 1 查询，$a_i$ 表示查询的 $k$ 值，$b_i$ 始终为 $0$。
  • 若 $t_i = 2$，这是一类 2 查询，$a_i$ 和 $b_i$ 分别表示范围 $[a, b]$。

对于每个类型 1 查询，输出对应的结果，每个结果输出一次之后需要换行。

本翻译由 AI 自动生成