题面描述

在一个房间内有 $2^n$ 盏灯，每一盏灯都有一个独一无二的 $0 \sim (2^n - 1)$ 的编号。一开始，有部分的灯是熄灭的，有部分灯是点亮的。

有两个法师在一起研究这些灯。他们是明亮法师（Wizard of Brightness）和黑暗法师（Wizard of Darkness）。他们各有一个法术：

• 当明亮法师施法的时候，所有的灯的状态都会翻转。熄灭的灯将会被点亮，亮着的灯将会被熄灭。

• 当黑暗法师施法的时候，这些灯的状态将会发生巨大的变化。假设施法之前一共有 $m$ 盏灯是熄灭的，比方说编号为 $a_0, \dots, a_{m - 1}$ 的灯，那么，他会同时对于 $\{a_0, \dots, a_{m - 1}\}$ 的所有子集，熄灭编号为子集的异或和的灯。

  例如说，集合 $\{1, 2\}$ 的异或和为 $1 \oplus 2 = 3$，集合 $\{\}$ 的异或和为 $0$。

  注意这 $2^m$ 次操作是同时进行的，就算他多熄灭了一盏灯，操作的次数（$2^m$）也不会变化。如果一盏本来就是灭着的灯被熄灭，则不会发生变化。

为了练习法术，两个法师准备了一个施法序列 $S$，这个序列仅由 BD 组成，表示这次是明亮法师（B）还是黑暗法师（D）进行施法。在一次练习中，他们会从 $S$ 中截取一段区间 $[l_i, r_i]$，从左往右依次施法。

为了观察效果，他们还打算进行时光倒流。这就使得他们的时间线不是线性的，而是一个树状结构。他们可以回到任意一个时间节点，也可以在某个时间点进行练习，达到另外的一个时间节点。他们还可以反复观察两个时间节点之间的过程。

简单来说，他们的练习和观察包含三种操作：

1. 给定 $t, l_i, r_i$，表示回到第 $t$ 个时间节点，并且截取 $S$ 的 $[l_i, r_i]$ 区间进行练习，练习结束后，灯的状态被记录在了一个新的时间节点。这个时间节点的编号为原有的时间节点个数。 初始时只有一个时间节点，该时间节点的编号为 $0$。在这个时间节点中灯的状态给定。
2. 给定 $t, p$，表示回到第 $t$ 个时间节点，观察编号为 $p$ 的那盏灯是否被熄灭。
3. 给定 $t, p$，设第 $t$ 个时间节点是由从时间节点 $s$ 开始的一次练习产生的，观察编号为 $p$ 的灯在这次练习中，有几次施法后是熄灭的。

输入格式

第一行三个整数 $n, |S|, q$，表示有 $2^n$ 盏灯，施法序列 $S$ 的长度，练习和观察的总数。

第二行 $2^n$ 个整数，给出第 $0$ 个时间节点的状态。若第 $i$ 个整数为 $1$，说明在第 $0$ 个时间节点中编号为 $i - 1$ 的灯是熄灭的。若第 $i$ 个整数位 $0$，说明第 $0$ 个时刻中编号为 $i-1$ 的灯是亮着的。

第三行包含 $|S|$ 个字符，表示 $S$。每个字符是 BD 之一，字符 B 表示当前是明亮法师施法，D 表示是黑暗法师施法。

接下来 $q$ 行，每行都遵循下列的一种格式：

• 1 t l r，表示第一种操作（进行练习）。
• 2 t p，表示第二种操作（观察 $t$ 时间节点的第 $p$ 盏灯是否熄灭）。
• 3 t p，表示第三种操作（观察到 $t$ 的那次练习中，第 $p$ 盏灯有几次是熄灭的）。

输出格式

对于三种操作，每行输出一个数：

• 对于第一种操作（进行练习），输出练习结束后，熄灭的灯的数量。
• 对于第二种操作（观察某时间节点的某盏灯），若灯熄灭，则输出 1，否则输出 0。
• 对于第三种操作（观察熄灭次数），输出这一盏灯处于熄灭的施法次数。

样例

2 5 5
0 0 1 1
BDBDB
1 0 1 2
1 1 1 5
2 2 1
2 1 2
3 1 3

2
3
1
1
0

说明/提示

在第 $0$ 个时间节点中，熄灭的灯有 $2, 3$。

在第 $1$ 个时间节点中，熄灭的灯有 $0, 1$。

在第 $2$ 个时间节点中，熄灭的灯有 $1, 2, 3$。

在 $0 \to 1$ 的那次练习中，第 $3$ 盏灯在 B 操作中被点亮，在 D 操作中仍然处于点亮状态，故有 $0$ 次施法后，这盏灯是熄灭的。

在所有数据中，$1 \le n \le 18$，$1 \le |S|, q \le 2 \times 10^5$。

保证 $S$ 只含有 BD 中的字符。

对于三种操作，保证 $t \lt$ 操作前的时间节点数。另外：

• 第一种操作，保证 $1 \le l_i \le r_i \le |S|$。
• 第二种操作，保证 $0 \le p \lt 2^n$。
• 第三种操作，保证 $t \not= 0$ 且 $0 \le p \lt 2^n$。

注意时间节点从 $0$ 开始编号，$0$ 是初始给定的时间节点。