Rabbit's Tree Jumps

A rabbit is on one of the nodes of a complete binary tree with \(2^n-1\) nodes. The nodes of the tree are numbered from 1 to \(2^n-1\) in the standard way: for any node with index \(i\) that has children, its left child is \(2\times i\) and its right child is \(2\times i+1\). Note that a node either has no children or both children.

The rabbit has prepared a sequence \(op\) of length \(m\). Each element of \(op\) is one of \(\{1, 2, 3\}\), corresponding to the following jump operations:

• Operation 1: Jump to the left child (this operation is only valid if the current node has a left child).
• Operation 2: Jump to the right child (this operation is only valid if the current node has a right child).
• Operation 3: Jump to the parent (if the current node is the root, this operation is ignored).

The rabbit will perform queries of two types:

1. Query: Given a starting node \(x\) and an interval \([l, r]\) (1-indexed) of the \(op\) sequence, execute the operations \(op_l, op_{l+1}, \ldots, op_r\) in order. For each operation, if the jump is valid, the rabbit moves accordingly; if an operation is invalid, it is ignored.
2. Update: Modify the operation at a given position in \(op\) to a new value.

Your task is to process all queries. For each query of the first type, output the final node where the rabbit lands. The complete binary tree has \(2^n-1\) nodes, so any jump that would move outside this range is ignored.

Note: All formulas are presented in LaTeX format.

inputFormat

The first line contains three integers \(n\), \(m\), and \(q\) where \(n\) defines the complete binary tree with \(2^n-1\) nodes, \(m\) is the length of the operation sequence, and \(q\) is the number of queries.

The second line contains \(m\) integers, each being 1, 2, or 3, representing the initial \(op\) sequence.

The following \(q\) lines each represent a query and are in one of the following formats:

• Q x l r: A query in which the rabbit starts at node \(x\) and performs operations from index \(l\) to \(r\) (inclusive).
• U pos v: An update query that sets \(op[\mathit{pos}] = v\) (\(v\) is one of 1, 2, 3).

outputFormat

For each query of type Q, output a single line with one integer indicating the node where the rabbit ends up after performing the specified operations.

sample

3 5 4
1 2 3 1 2
Q 1 1 3
Q 3 2 5
U 3 1
Q 3 2 5

2
6
7