年轻的优素福（Jusuf）有 $N$ 张牌，从左到右排成一排，编号为 $1$ 到 $N$。每张牌都有一个力量值，记为 $p_i$。优素福想要为即将到来的比赛做准备，因此他想尝试在牌之间进行对决，并用他从祖父那里得到的其他牌来替换他牌堆中的牌。优素福总共会进行 $Q$ 次查询，每次查询属于以下两种类型之一：

• 1 i r - 表示优素福将位置 $i$ 处的牌替换为力量值为 $r$ 的新牌。
• 2 l k - 优素福将想象一场包含 $2^k$ 张牌的对决，从第 $l$ 张牌开始，到第 $l + 2^k - 1$ 张牌结束，并大喊“决斗时间到了！”。对决将分 $k$ 个回合进行。在每个回合中，优素福会观察相邻的牌对（第一张和第二张，第三张和第四张，以此类推）并比较它们的力量值。设一对牌的力量值为 $A$ 和 $B$。力量值较大的牌获胜，其新的力量值将变为 $|A - B|$（无论哪张牌获胜）。如果两张牌的力量值相等，则对决结果不确定，随机一张牌获胜，其力量值变为 $0$。输掉的牌将不再参加后续的回合。请注意，经过 $k$ 个这样的回合后，将只剩下一张牌。优素福想知道这张牌的力量值！

输入格式

第一行包含自然数 $N$ 和 $Q$。

下一行包含 $N$ 个整数 $p_i$ ($0 \le p_i \le 10^9$)，表示牌的力量值。

接下来的 $Q$ 行包含对应于题目描述的查询。

对于每个类型 1 的查询，满足 $1 \le i \le N$ 且 $0 \le r \le 10^9$。

对于每个类型 2 的查询，满足 $1 \le l \le N$ 且 $1 \le l + 2^k - 1 \le N$。

输出格式

对于每个类型 2 的查询，需要输出 $k$ 个回合后最终牌的力量值。

子任务

在所有子任务中，满足 $2 \le N \le 200\,000$ 且 $1 \le Q \le 200\,000$。

样例

输入 1

5 3
4 8 2 0 7
2 1 2
1 1 9
2 2 1

输出 1

2
6

输入 2

8 6
1 2 3 4 5 6 7 8
2 1 3
1 4 1
1 7 3
2 1 3
1 2 100
2 2 2

输出 2

0
3
93

输入 3

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

输出 3

2
1
0

说明

第一个样例的说明：

在第一个查询中，牌在回合中变化如下： $(4, 8, 2, 0) \to (4, 2) \to (2)$

在第三个查询中，牌在回合中变化如下： $(8, 2) \to (6)$