CF1725K.Kingdom of Criticism

Pak Chanek is visiting a kingdom that earned a nickname "Kingdom of Criticism" because of how often its residents criticise each aspect of the kingdom. One aspect that is often criticised is the heights of the buildings. The kingdom has $N$ buildings. Initially, building $i$ has a height of $A_i$ units.

At any point in time, the residents can give a new criticism, namely they currently do not like buildings with heights between $l$ and $r$ units inclusive for some two integers $l$ and $r$. It is known that $r-l$ is always odd.

In $1$ minute, the kingdom's construction team can increase or decrease the height of any building by $1$ unit as long as the height still becomes a positive number. Each time they receive the current criticism from the residents, the kingdom's construction team makes it so that there are no buildings with heights between $l$ and $r$ units inclusive in the minimum time possible. It can be obtained that there is only one way to do this.

Note that the construction team only cares about the current criticism from the residents. All previous criticisms are forgotten.

There will be $Q$ queries that you must solve. Each query is one of the three following possibilities:

• 1 k w: The kingdom's construction team changes the height of building $k$ to be $w$ units ($1 \leq k \leq N$, $1 \leq w \leq 10^9$).
• 2 k: The kingdom's construction team wants you to find the height of building $k$ ($1 \leq k \leq N$).
• 3 l r: The residents currently do not like buildings with heights between $l$ and $r$ units inclusive ($2 \leq l \leq r \leq 10^9-1$, $r-l$ is odd).

Note that each change in height still persists to the next queries.

帕克·查内克正在访问一个因其居民频繁批评王国各个方面的行为而获得“批评王国”绰号的国度。其中，建筑物的高度是被批评最多的方面之一。该国度共有 $N$ 座建筑物，初始时第 $i$ 座建筑物的高度为 $A_i$ 个单位。

在任意时刻，居民都可能提出一项新的批评：他们当前不喜欢高度在 $l$ 到 $r$（含端点）之间的所有建筑物，其中 $l$ 和 $r$ 是两个整数。已知 $r - l$ 恒为奇数。

王国施工队每分钟可将任意一座建筑物的高度增加或减少 $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$ 为奇数）。

注意：每次高度更改的效果将持续到后续所有查询中。

The first line contains a single integer $N$ ($1 \leq N \leq 4 \cdot 10^5$) — the number buildings in the kingdom.

The second line contains $N$ integers $A_1, A_2, \ldots, A_N$ ($1 \leq A_i \leq 10^9$) — the initial heights of the buildings.

The next line contains a single integer $Q$ ($1 \leq Q \leq 4 \cdot 10^5$) — the number of queries.

The $j$-th of the next $Q$ lines contains the $j$-th query as described. There is at least one query of type $2$.

第一行包含一个整数 $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$ 的查询。

For each query of type $2$, output a line containing an integer representing the height of the building asked.

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

After the $1$-st query, the height of each building is $2, 6, 5, 6, 10$.

After the $3$-rd query, the height of each building is $3, 6, 5, 6, 10$.

After the $4$-th query, the height of each building is $2, 7, 7, 7, 10$.

After the $5$-th query, the height of each building is $2, 7, 7, 7, 10$.

After the $6$-th query, the height of each building is $2, 9, 7, 7, 10$.

第一次查询后，每栋建筑的高度为 $2, 6, 5, 6, 10$。

第三次查询后，每栋建筑的高度为 $3, 6, 5, 6, 10$。

第四次查询后，每栋建筑的高度为 $2, 7, 7, 7, 10$。

第五次查询后，每栋建筑的高度为 $2, 7, 7, 7, 10$。

第六次查询后，每栋建筑的高度为 $2, 9, 7, 7, 10$。