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$）。

第 $1$ 行，$3$ 个整数 $n,m,q$； 第 $2$ 行，$2^n$ 个整数 $a_0,a_1,\cdots,a_{2^n-1}$； 第 $3$ 行，$1$ 个字符串 $S$（下标从 $1$ 开始），对于每个满足 $1\le i\le m$ 的整数 $i$，如果 $S_i$ 是 `B`，那么表示 Happybob 释放了一次一技能，否则他释放了一次二技能； 接下来 $q$ 行，每行 $3$ 个或 $4$ 个非负整数，表示一个询问。

$q$ 行，第 $i$ 行一个整数，表示第 $i$ 个询问的结果。

3 10 6
0 1 0 1 0 1 0 0
BDBDBDDBBD
1 0 1 5
1 0 8 10
1 0 6 8
2 2 4
2 3 4
3 1 3

7
8
0
1
0
2

### 样例说明 | 版本编号 | 灯的状态 | | --- | --- | | $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<2^n$。保证 $S$ 中只含字符 `B` 与 `D`（可能不含 `B` 或不含 `D`），且 $S$ 的长度为 $m$。