给定一个无向图 $G$，它有 $2^N + 1$ 个顶点和 $2^{N+1} - 1$ 条边。顶点编号为 $0, 1, \dots, 2^N$，边编号为 $1, 2, \dots, 2^{N+1} - 1$。

图 $G$ 中的每条边属于 $N+1$ 种类型之一，从类型 $0$ 到类型 $N$。对于类型 $i$ ($0 \le i \le N$)，恰好有 $2^i$ 条边，编号为 $2^i + 0, 2^i + 1, \dots, 2^i + (2^i - 1)$。编号为 $2^i + j$ ($0 \le j \le 2^i - 1$) 的边是一条长度为 $C_{2^i+j}$ 的无向边，连接顶点 $j \times 2^{N-i}$ 和顶点 $(j + 1) \times 2^{N-i}$。

例如，当 $N = 3$ 时，$G$ 的结构如下图所示：

你需要处理 $Q$ 个查询。查询有两种类型：

• $1 \ j \ x$：将边 $j$ 的长度修改为 $x$。
• $2 \ s \ t$：求从顶点 $s$ 到顶点 $t$ 的最短路径长度。

输入格式

输入按以下格式给出。注意顶点编号从 $0$ 开始，边编号从 $1$ 开始。

$N$ $C_1 \ C_2 \ \dots \ C_{2^{N+1}-1}$ $Q$ $\text{query}_1$ $\text{query}_2$ $\vdots$ $\text{query}_Q$

其中 $\text{query}_i$ 表示第 $i$ 个查询。每个查询的格式如下：

$1 \ j \ x$ $2 \ s \ t$

• 所有输入值均为整数。
• $1 \le N \le 18$
• $1 \le C_j \le 10^7$ ($1 \le j \le 2^{N+1} - 1$)
• $1 \le Q \le 2 \times 10^5$
• 在查询 $1 \ j \ x$ 中，$1 \le j \le 2^{N+1} - 1$ 且 $1 \le x \le 10^7$。
• 在查询 $2 \ s \ t$ 中，$0 \le s < t \le 2^N$。
• 至少包含一个 $2 \ s \ t$ 查询。

输出格式

设 $m$ 为类型 $2 \ s \ t$ 的查询数量。输出 $m$ 行，其中第 $i$ 行包含第 $i$ 个 $2 \ s \ t$ 查询的答案。

样例

样例输入 1

3
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

说明

• 在第一个查询中，使用边 $8$，路径 $0 \to 1$ 的总距离为 $2$。
• 在第二个查询中，使用边 $2$，路径 $0 \to 4$ 的总距离为 $1$。
• 在第三个查询中，使用边 $6$，路径 $4 \to 6$ 的总距离为 $4$。
• 在第四个查询中，使用边 $2, 1$，路径 $4 \to 0 \to 8$ 的总距离为 $8$。
• 在第五个查询中，使用边 $11, 6, 13$，路径 $3 \to 4 \to 6 \to 5$ 的总距离为 $17$。
• 在第六个查询中，边 $6$ 的长度从 $4$ 更新为 $30$。
• 在第七个查询中，使用边 $11, 12$，路径 $3 \to 4 \to 5$ 的总距离为 $18$。
• 在第八个查询中，使用边 $2, 1, 15, 14$，路径 $4 \to 0 \to 8 \to 7 \to 6$ 的总距离为 $13$。
• 在第九个查询中，边 $1$ 的长度从 $7$ 更新为 $10000000$。
• 在第十个查询中，使用边 $2, 3$，路径 $0 \to 4 \to 8$ 的总距离为 $15$。