P10926 Happybob's Magic (UBC001F)

Happybob 正在游戏里研究一排灯，总共 $2^n$ 个，编号为 $0\sim 2^n-1$。Happybob 有两个技能。 一技能（按下 `B` 释放）释放一次，所有的灯亮变成灭，灭变成亮。 二技能（按下 `D` 释放）就厉害了，每释放一次，假设释放前的所有亮着的灯的编号组成的集合是 $X$，那么对于 $X$ 的**所有 $2^{|X|}$ 个子集（包含空集）** $Y$，Happybob 会把第 $\bigoplus(Y)$ 盏灯点亮。这里的 $|X|$ 表示 $X$ 集合的大小，$\bigoplus(Y)$ 表示将集合 $Y$ 的所有元素进行二进制按位异或得到的结果。特别地，$\bigoplus(\varnothing) = 0$。 现在有一个 `B`，`D` 构成的施法序列 $S(|S|=m)$（意义如上），一个灯的初始状态序列（第 $0$ 个版本）$a_0,a_1,\cdots,a_{2^n-1}$，以及一个变量 $vid=0$。Happybob 有 $q$ 次询问，每次询问可能是： 1. `1 v l r`：将 $vid$ 加 $1$，对第 $v$ 个版本依次执行 $S_l$ 到 $S_r$ 的施法操作，将结果存入第 $vid$ 个版本中，并问第 $vid$ 个版本中有多少盏灯是亮的。 2. `2 v k`：问第 $v$ 个版本的第 $k$ 盏灯是不是亮的。是输出 $1$，否则输出 $0$。 3. `3 v k`：设第 $v$ 个版本是从第 $v'$ 个版本执行了 $t$ 次施法操作变过来的，问有多少次施法操作之后，第 $k$ 盏灯是亮的（原来是亮的不算）。 对于第三种询问，这里的 $v'$ 和 $t$ 具体定义如下：假设进行某一次第一种询问后 $vid = v$，则 $v'$ 等于那一次询问给定的 $v$，$t$ 即那一次询问给定的操作序列 $S_{l\cdots r}$ 的长度。 保证 $0\le v\le vid$（如果是第一个操作，则是加 $1$ 前的 $vid$；如果是第三个操作，还保证 $v>0$）。

无

无

### 样例说明 | 版本编号 | 灯的状态 | | --- | --- | | $0$ | $01010100$ | | $1$ | $01111111$ | | $2$ | $11111111$ | | $3$ | $00000000$ | 对于最后一次询问，每次施法操作后的状态如下： | 操作 | 灯的状态 | | --- | --- | | 初始值 | $01010100$ | | `B` | $10101011$ | | `BD` | $111\red11111$ | | `BDB` | $00000000$ | | `BDBD` | $10000000$ | | `BDBDB` | $011\red11111$ | 第 $3$ 盏灯亮了 $2$ 次。 ### 数据范围 对于 $100\%$ 的数据， $1\le n\le 18$，$1\le q\le 2\times 10^5$，$a_i\in\{0, 1\}$，$1\le l\le r\le m\le 2\times 10^5$，$0\le k