题目描述

格雷码是一种二进制数字编码系统，其相邻两个数值之间仅有一位二进制位不同。这一特性使其在数字通信与测量系统中能够有效减少错误，因而得到了广泛应用。格雷码还以反射性与循环性著称，有助于消除随机采样过程中产生的显著误差。该编码由 Frank Gray 于 20 世纪 40 年代发明，并拥有多种构造方法。

一个 $n$ 位格雷码 $G_n=[G_{n,0},G_{n,1},\cdots,G_{n,2^n-1}]$ 可通过如下算法生成：

• $1$ 位格雷码由两个二进制数 $0$ 与 $1$ 组成，即 $G_1=[0,1]$。
• $(n+1)$ 位格雷码的前 $2^n$ 个二进制数与 $n$ 位格雷码完全相同；后 $2^n$ 个二进制数则是将 $n$ 位格雷码按 逆序 排列后，每个数再加上 $2^n$ 得到。即 $G_{n+1}=[G_{n,0},G_{n,1},\cdots,G_{n,2^n-1},G_{n,2^n-1}+2^n,G_{n,2^n-2}+2^n,\cdots,G_{n,0}+2^n]$。

例如，$G_2=[0,1,3,2]$，$G_3=[0,1,3,2,6,7,5,4]$。

现有一个长度为 $2^n$ 的数组 $a_0,a_1,\cdots,a_{2^n-1}$。初始时，对所有 $i\in\{0,1,\cdots,2^n-1\}$，均有 $a_i=i$。接下来将对该数组执行 $q$ 次操作，每次操作属于以下两种类型之一：

• 给定 $m$ 及 $k_1,k_2,\cdots,k_m$，依次对 $i=1,2,\cdots,m$ 按递增顺序，对每个 $j\in\{0,1,\cdots,2^{k_i}-1\}$，若 $a_j<2^{k_i}$，则令 $a_j=G_{k_i,a_j}$；否则不对 $a_j$ 做任何更改。
• 给定 $p$，查询 $a_p$ 的值。

请你按顺序输出每次查询的结果。

输入格式

输入的第一行包含两个整数，分别为 $n$（$1\le n\le 10$）与 $q$（$1\le q\le 5000$）。

接下来的 $q$ 行描述各次操作。每行以一个整数 $\text{op}$（$\text{op}\in\{1,2\}$）开始，表示操作的类型。

• 若 $\text{op}=1$，则该行接下来是一个整数 $m$（$1\le m\le 5000$）以及 $m$ 个整数 $k_1,k_2,\cdots,k_m$（对所有 $i\in\{1,2,\cdots,m\}$ 均有 $1\le k_i\le n$），表示一次第 1 类操作。
• 若 $\text{op}=2$，则该行接下来是整数 $p$（$0\le p< 2^n$）的 二进制形式（不含前导零），表示一次参数为 $p$ 的第 2 类操作。

保证所有第 1 类操作中的 $m$ 之和不超过 $5000$。

输出格式

对于每次第 2 类操作，输出其结果的 二进制形式（不含前导零），每个结果占一行。

3 4
2 0
1 4 1 2 3 2
2 100
2 10

0
110
11

提示

初始时，$[a_0,a_1,\cdots,a_{2^n-1}]=[0,1,2,3,4,5,6,7]$。

经过第二个操作后，$[a_0,a_1,\cdots,a_{2^n-1}]=[0,1,3,2,6,7,5,4]$。

翻译由 DeepSeek V3.2 完成