题目描述

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

提示

样例说明

对于最后一次询问，每次施法操作后的状态如下：

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