P10926 Happybob's Magic (UBC001F)

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$.

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 $q$ lines. The $i$-th line contains one integer, representing the answer to the $i$-th query.

### Sample Explanation | Version ID | Light states | | --- | --- | | $0$ | $01010100$ | | $1$ | $01111111$ | | $2$ | $11111111$ | | $3$ | $00000000$ | For the last query, the states after each cast are as follows: | Operation | Light states | | --- | --- | | Initial | $01010100$ | | `B` | $10101011$ | | `BD` | $111\red11111$ | | `BDB` | $00000000$ | | `BDBD` | $10000000$ | | `BDBDB` | $011\red11111$ | 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