题目描述

仵沉蛋有一棵 zkw 线段树，它是一棵满二叉树，它的每个节点 $i$ 都有其对应的区间 $[l_i,r_i]$ 和权值 $w_i$。

根节点 $1$ 是该线段树的根节点，满足 $l_1=1,r_1=2^n$。

对于每个满足 $r_i>l_i$ 的节点 $i$，令 $M_i=\lfloor\dfrac{l_i+r_i}{2}\rfloor$，则：

节点 $i$ 的左儿子为节点 $2\times i$，并且满足 $l_{2\times i}=l_i,r_{2\times i}=M_i$。

节点 $i$ 的右儿子为节点 $2\times i+1$，并且满足 $l_{2\times i+1}=M_i+1,r_{2\times i+1}=r_i$。

对于 $l_i=r_i$ 的节点 $i$，该节点为叶子。

肚子的有一张包含 $2^n+1$ 个节点的图，节点编号从 $0$ 到 $2^n$。他想要对于 zkw 线段树上的每个节点 $i$，在 $l_i-1$ 和 $r_i$ 间连边权为 $w_i$ 的无向边。

现在他要求你执行两种类型共 $q$ 个操作：

• 1 j v ：将 $w_j$ 变为 $v$。
• 2 s t ：求出图上点 $s$ 和点 $t$ 间的最短路。

输入格式

第一行两个整数 $n$ 和 $o$，其中 $o$ 表示子任务编号。

第二行包含 $2^{n+1}-1$ 个整数，第 $i$ 个表示 $w_i$。

第三行一个整数 $q$，表示操作的个数。

接下来 $q$ 行每行三个整数，表示一个操作。

输出格式

对于每个询问操作，输出一行一个整数表示答案。

样例输入 1

3 0
7 1 14 3 9 4 8 2 6 5 5 13 8 2 3
10
2 0 1
2 0 4
2 4 6
2 4 8
2 3 5
1 6 30
2 3 5
2 4 6
1 1 10000000
2 0 8

样例输出 1

2
1
4
8
17
18
13
15

样例 2~7

见附加文件。分别满足每个子任务的限制。

数据范围

对于所有数据满足 $1\le n\le 18,1\le w_i\le 10^7,1\le q\le 2\times 10^5$。