Description

One day, a rabbit is on a node of a perfect binary tree with $2^n-1$ nodes, and he plans to perform several jumps of the following types:

• Jump to the left child of the current node. It is guaranteed that the node has a left child.
• Jump to the right child of the current node. It is guaranteed that the node has a right child.
• Jump to the parent of the current node. If the current node is the root, ignore this operation.

For node $i$, it either has no children, or it has a left child $2 \times i$ and a right child $2 \times i + 1$.

The rabbit will jump in a planned way. He writes down a sequence $op$ of length $m$. Each number in $op$ is one of $1$, $2$, or $3$. Operation $i$ corresponds to the $i$-th jump type listed above from top to bottom.

Each time, the rabbit chooses an interval $[l,r]$ and performs the jumps $op_l,op_{l+1},\ldots,op_r$ in order.

Sometimes, the rabbit will modify the $op$ value at a position.

Now you need to determine which node the rabbit ends up at for each query.

Reading the sample explanation can help you understand the statement better.

Input Format

The first line contains three integers $n, m, q$, representing the exponent determining the tree size, the length of $op$, and the number of operations.

The second line contains $m$ integers $op_{1,2,\ldots,m}$, representing the initial sequence.

The next $q$ lines each contain an integer $type$. If $type$ is $1$, then three integers $s,l,r$ follow, describing the starting node and the interval of jumps to perform. If $type$ is $2$, then two integers $x,y$ follow, describing the position to modify and the new value.

Output Format

For each query with $type=1$, output one number, the node where the rabbit ends up after the jumps.

3 5 4
1 2 3 3 1
1 3 4 5
1 2 2 4
2 3 1
1 1 2 3

2
1
6

Hint

The red edges show the path of the first jump, the blue edges the second, and the green edges the third.

The constraints and characteristics of all testdata are shown in the table below:

For $100\%$ of the data, $1\leq n \leq 30$, $1\leq m,q \leq 5 \times 10^5$, and $1\leq op_i\leq 3$.

Translated by ChatGPT 5