Happybob's Light Skills

In this problem, Happybob is investigating a row of lights. There are \(2^n\) lights, numbered from \(0\) to \(2^n-1\). He has two skills:

• Skill B (triggered by pressing the key B): When released, every light toggles its state (turned on lights become off and vice versa).
• Skill D (triggered by pressing the key D): When released, let \(X\) be the set of indices of lights that are on immediately before the skill. Then for every subset \(Y \subseteq X\) (including the empty set) the light numbered \(\bigoplus(Y)\) is turned on. Here, \(|X|\) denotes the size of \(X\) and \(\bigoplus(Y)\) denotes the bitwise XOR of all elements in \(Y\), with the convention that \(\bigoplus(\varnothing)=0\).

You are given a spell sequence S of length \(m\) consisting only of the characters B and D (the meaning of each character is as described above), an initial configuration (version 0) of the lights \(a_0,a_1,\dots,a_{2^n-1}\) and a variable vid = 0. Then you need to process \(q\) queries. There are three types of queries:

1. 1 v l r: Increase vid by 1. Starting from version v, apply the spells from S_l to S_r in order. Save the resulting configuration as version vid and output the number of lights that are on in version vid.
2. 2 v k: Query whether in version v the light numbered k is on. Output 1 if it is, otherwise output 0.
3. 3 v k: Suppose version v was generated from some version v' by applying a sequence of \(t\) spell operations. In this query, output how many of those \(t\) operations changed the state of the k-th light from off to on (if it was already on originally, that operation is not counted).

Note: For query type 3, when a type 1 query is performed (which creates a new version), record the base version v' and the length \(t=r-l+1\) of the spell sequence applied. Then query 3 v k asks, starting with the configuration of version v', if you apply the spells one by one, in how many of these steps (immediately after an operation) the k-th light becomes on given that it was off before that operation.

Input Format: The input begins with three integers \(n, m, q\). Then follows \(2^n\) integers (each either 0 or 1) representing the initial state of the lights (version 0). Next is a string S of length \(m\) consisting only of characters B and D. Finally, there are \(q\) queries, one per line, in one of the three forms described above. In spell operations, the indices for S are 1-indexed.

Output Format: For each query, output the answer in order. For query type 1, output the count of on lights in the newly created version; for query type 2, output 1 if the queried light is on and 0 otherwise; and for query type 3, output the corresponding count as described.

inputFormat

The first line contains three integers \(n\), \(m\), and \(q\).

The second line contains \(2^n\) integers, each 0 or 1, representing the initial state of the lights (version 0).

The third line contains a string S of length \(m\) consisting only of the characters B and D.

Each of the next \(q\) lines describes a query in one of the formats: 1 v l r, 2 v k, or 3 v k. For spell operations, the indices for S are 1-indexed.

outputFormat

For each query, output a single integer: for type 1 queries, the number of lights on in the new version; for type 2 queries, 1 if the queried light is on and 0 otherwise; and for type 3 queries, the count of operations (from off to on) for the specified light.

sample

2 3 4
1 0 1 0
BDB
1 0 1 2
2 1 2
1 1 2 3
3 2 3

4
1
0
0