Problem Description

Happybob is studying a row of lights in a game. There are $2^n$ lights in total, numbered from $0$ to $2^n-1$. Happybob has two skills.

Skill 1 (press B to cast): Each time it is cast, all lights are toggled: on becomes off, and off becomes on.

Skill 2 (press D to cast) is stronger. Each time it is cast, suppose the set of indices of all lights that are on before casting is $X$. Then, for all $2^{|X|}$ subsets (including the empty set) $Y$ of $X$, Happybob will turn on the light with index $\bigoplus(Y)$. Here $|X|$ is the size of set $X$, and $\bigoplus(Y)$ is the bitwise XOR of all elements in set $Y$. In particular, $\bigoplus(\varnothing) = 0$.

Now you are given a casting sequence $S$ consisting of B and D $(|S|=m)$ (with the meanings above), an initial light state sequence (version $0$) $a_0,a_1,\cdots,a_{2^n-1}$, and a variable $vid=0$. Happybob has $q$ queries, and each query can be one of the following:

1. 1 v l r: Increase $vid$ by $1$. Starting from version $v$, apply the casting operations $S_l$ through $S_r$ in order, store the result as version $vid$, and ask how many lights are on in version $vid$.
2. 2 v k: Ask whether the $k$-th light in version $v$ is on. Output $1$ if it is on, otherwise output $0$.
3. 3 v k: Suppose version $v$ was obtained from version $v'$ by applying $t$ casting operations. Ask, among these casts, after how many casts the $k$-th light is on (do not count the times when it was already on initially).

For the third type of query, $v'$ and $t$ are defined as follows: if after some type 1 query we have $vid = v$, then $v'$ is the value $v$ given in that query, and $t$ is the length of the operation sequence $S_{l\cdots r}$ given in that query.

It is guaranteed that $0\le v\le vid$ (for a type 1 query, this refers to $vid$ before adding $1$; for a type 3 query, it is also guaranteed that $v>0$.

Input Format

Line $1$: three integers $n,m,q$.

Line $2$: $2^n$ integers $a_0,a_1,\cdots,a_{2^n-1}$.

Line $3$: a string $S$ (1-indexed). For each integer $i$ with $1\le i\le m$, if $S_i$ is B, it means Happybob casts skill 1 once; otherwise, he casts skill 2 once.

The next $q$ lines: each line contains $3$ or $4$ non-negative integers, representing a query.

Output Format

Output $q$ lines. The $i$-th line contains one integer, representing the answer to the $i$-th query.

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

Hint

Sample Explanation

For the last query, the states after each cast are as follows:

The 3rd light is turned on $2$ times.

Constraints

For $100\%$ of the testdata: $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$. It is guaranteed that $S$ contains only characters B and D (it may contain no B or no D), and the length of $S$ is $m$.

Translated by ChatGPT 5