Pak Chanek 正在访问一个王国,该王国因其居民经常批评该王国的各个方面而赢得了“批评王国”的绰号。经常受到批评的一方面是建筑物的高度。该王国有 $$$N$$$ 建筑物。最初,建筑物 $$$i$$$ 的高度为 $$$A_i$$$ 单位。
在任何时间点,居民都可以提出新的批评,即他们目前不喜欢高度在$$$l$$$和$$$r$$$单位之间的建筑物,包括两个整数$$$l$$$和$$$r$$$。已知 $$$r-l$$$ 始终为奇数。
在$$$1$$$分钟内,王国建设队可以将任何建筑物的高度增加或减少$$$1$$$单位,只要高度仍然为正数。每次收到居民的当前批评,王国的建筑团队都会在尽可能短的时间内,确保没有高度在 $$$l$$$ 和 $$$r$$$ 单位之间的建筑物。可以看出,只有一种方法可以做到这一点。
注意,施工队只关心目前居民的批评。以前所有的批评都被忘记了。
您必须解决 $$$Q$$$ 查询。每个查询都是以下三种可能性之一:
- 1 k w:王国的建筑团队将建筑物的高度 $$$k$$$ 更改为 $$$w$$$ 单位($$$1 \leq k \leq N$$$、$$$1 \leq w \leq 10^9$$$)。
- 2 k:王国的建筑团队希望你找到建筑物的高度 $$$k$$$ ($$$1 \leq k \leq N$$$)。
- 3 l r:居民目前不喜欢高度在 $$$l$$$ 和 $$$r$$$ 单位之间(含 $$$2 \leq l \leq r \leq 10^9-1$$$,$$$r-l$$$ 为奇数)的建筑物。
请注意,高度的每次更改仍会持续到下一个查询。
输入
第一行包含一个整数 $$$N$$$ ($$$1 \leq N \leq 4 \cdot 10^5$$$) — 王国中的建筑物数量。
第二行包含 $$$N$$$ 整数 $$$A_1, A_2, \ldots, A_N$$$ ($$$1 \leq A_i \leq 10^9$$$) — 建筑物的初始高度。
下一行包含一个整数 $$$Q$$$ ($$$1 \leq Q \leq 4 \cdot 10^5$$$) — 查询数。
接下来的 $$$Q$$$ 行中的第 $$$j$$$ 行包含第 $$$j$$$ 个查询,如所述。至少有一个 $$$2$$$ 类型的查询。
输出
对于 $$$2$$$ 类型的每个查询,输出一行,其中包含表示所询问建筑物高度的整数。
示例
输入 #1
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
输出 #1
10 7 9 7
注意
经过$$$1$$$-st查询后,每栋建筑的高度为$$$2, 6, 5, 6, 10$$$。
$$$3$$$-rd查询后,每栋建筑的高度为$$$3, 6, 5, 6, 10$$$。
第 $$$4$$$ 次查询后,每个建筑物的高度为 $$$2, 7, 7, 7, 10$$$。
第 $$$5$$$ 次查询后,每个建筑物的高度为 $$$2, 7, 7, 7, 10$$$。
第 $$$6$$$ 次查询后,每个建筑物的高度为 $$$2, 9, 7, 7, 10$$$。