P16603 [SYSUCPC 2025] Gray Transform (Weakened)

格雷码是一种二进制数字编码系统，其相邻两个数值之间仅有一位二进制位不同。这一特性使其在数字通信与测量系统中能够有效减少错误，因而得到了广泛应用。格雷码还以反射性与循环性著称，有助于消除随机采样过程中产生的显著误差。该编码由 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

输入的第一行包含两个整数，分别为 $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 类操作，输出其结果的 **二进制形式**（不含前导零），每个结果占一行。

初始时，$[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 完成