K. 批评王国

每次测试的时间限制：3 秒
每次测试的内存限制：512 兆字节

帕克·查内克正在访问一个因居民喜欢批评王国各个方面而被称为“批评王国”的王国。建筑物高度是经常被批评的方面之一。这个王国有 $N$ 座建筑物。初始时，建筑物 $i$ 的高度为 $A_i$ 单位。

在任何时候，居民可以提出新的批评，即对于某两个整数 $l$ 和 $r$，他们当前不喜欢高度在 $[l, r]$ 单位之间（包含端点）的建筑物。已知 $r - l$ 总是奇数。

在 $1$ 分钟内，王国的施工队可以将任意建筑物的高度增加或减少 $1$ 单位，但高度必须保持为正整数。每次收到居民当前的批评时，施工队会用最短的时间使得不存在高度在 $[l, r]$ 单位之间的建筑物。可以证明，这样做的方式只有一种。

注意，施工队只关注居民当前的批评。所有以前的批评都会被遗忘。

将有 $Q$ 个查询需要你解决。每个查询是以下三种之一：

1. 1 k w：施工队将建筑物 $k$ 的高度改为 $w$ 单位（$1 \le k \le N$，$1 \le w \le 10^9$）。
2. 2 k：施工队想要你输出建筑物 $k$ 的高度（$1 \le k \le N$）。
3. 3 l r：居民当前不喜欢高度在 $[l, r]$ 单位之间的建筑物（$2 \le l \le r \le 10^9 - 1$，$r - l$ 为奇数）。

注意：每次高度修改会持续到后续查询中。

输入
第一行包含一个整数 $N$（$1 \le N \le 4 \times 10^5$）——王国的建筑物数量。
第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$（$1 \le A_i \le 10^9$）——建筑物的初始高度。
下一行包含一个整数 $Q$（$1 \le Q \le 4 \times 10^5$）——查询的数量。
接下来的 $Q$ 行中，第 $j$ 行包含第 $j$ 个查询，格式如上所述。至少有一个类型 2 的查询。

输出
对于每个类型 2 的查询，输出一行，包含所询问建筑物的高度。

示例

输入

5
2 6 5 6 2
9
1 5 10
2 5
1 1 3
3 3 6
3 8 9
1 2 9
2 3
2 2
2 4

输出

10
7
9
7

说明

• 在第 1 个查询后，各建筑高度为 $2, 6, 5, 6, 10$。
• 在第 3 个查询后，各建筑高度为 $3, 6, 5, 6, 10$。
• 在第 4 个查询后，各建筑高度为 $2, 7, 7, 7, 10$。
• 在第 5 个查询后，各建筑高度为 $2, 7, 7, 7, 10$。
• 在第 6 个查询后，各建筑高度为 $2, 9, 7, 7, 10$。