题目背景

兔子喜欢跳树。

题目描述

一天，兔子在一棵点数为 $2^n-1$ 完全二叉树上的一个结点上，他准备进行若干次如下的跳跃。

• 跳到这个点的左儿子，保证这个点有左儿子。
• 跳到这个点的右儿子，保证这个点有右儿子。
• 跳到这个点的父亲，若这个点是根，无视此操作。

其中，$i$ 号点要么没有儿子，要么有左儿子 $2 \times i$ 和右儿子 $2 \times i + 1$。

兔子会计划性地跳树，他写下了一个长度为 $m$ 的序列 $op$。$op$ 中的每个数都是 $1$, $2$, $3$ 中的一种。操作 $i$ 对应从上到下第 $i$ 种跳跃方式。

每次，兔子会选择一段区间 $[l,r]$，依次进行跳跃 $op_l,op_{l+1},\ldots,op_r$。

有时兔子会对一个点的 $op$ 值进行修改。

现在你需要求出兔子每次会跳到哪个结点。

阅读样例解释可以对题意获得更好的理解。

输入格式

第一行三个整数 $n, m, q$，表示树的大小的幂次、$op$ 的长度、操作的次数。

第二行包含 $m$ 个整数 $op_{1,2,\ldots,m}$，表示序列的初值。

接下来 $q$ 行，每行一个整数 $type$，若 $type$ 为 $1$，接下来三个整数 $s,l,r$，描述起点和进行跳跃的区间；若 $type$ 为 $2$ ，接下来两个整数 $x,y$，描述修改的位置与值。

输出格式

对于每一个 $type=1$，输出一个数，表示跳跃到的结点。

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

提示

其中红边为第一次跳跃的路径，蓝边为第二次，绿边为第三次。

所有测试数据的范围和特点如下表所示：

对于 $100\%$ 的数据，$1\leq n \leq 30$，$1\leq m,q \leq 5 \times 10^5$，$1\leq op_i\leq 3$。