题目描述

有 $N$ 位运动员，第 $i$ 位运动员的力量为 $a_i$。

你需要维护 $Q$ 次操作，每次操作为如下的形式之一：

• $1 \space x \space y$：表示将 $a_x$ 修改为 $y$。
• $2 \space l \space k$：假设将运动员 $l,l+1,\cdots,l+2^k-1$ 拿出来比赛：
  • 比赛进行 $k$ 轮，每轮中，相邻两位运动员会进行一次比赛（第 $1$ 位和第 $2$ 位比一次，第 $3$ 位和第 $4$ 位比一次，以此类推 ）。设一次比赛中两名运动员的力量为 $A$ 和 $B$，则力量大的运动员会获胜，力量变为 $|A-B|$ 后晋级下一轮，力量小的运动员被淘汰。特殊的，若 $A=B$，则随机一名运动员获胜，力量变为 $0$ 后晋级下一轮。你需要求出比完后剩下的那一位运动员的力量。
  • 注意这场比赛只是一场想象中的比赛，数组 $a$ 不会真正的改变。

输入格式

第一行两个整数 $N,Q$。

第二行 $N$ 个整数 $a_1,a_2,\cdots,a_n$。

接下来 $Q$ 行，每行表示一个操作。

输出格式

对于每个 $2$ 操作，输出一行一个整数表示答案。

样例

样例输入

6 6
5 2 8 2 2 1
2 1 2
1 2 1
1 4 1
1 5 1
1 6 5
2 3 2

样例输出

3
3

对于第一个 $2$ 操作：$\{5,2,8,2\} \rightarrow \{|5-2|,|8-2|\} \rightarrow \{3,6\} \rightarrow \{|3-6|\} \rightarrow \{3\}$。

经过一系列修改操作后，序列 $a$ 变为：$\{5,1,8,1,1,5\}$。

对于第二个 $2$ 操作：$\{8,1,1,5\} \rightarrow \{|8-1|,|1-5|\} \rightarrow \{7,4\} \rightarrow \{|7-4|\} \rightarrow \{3\}$。

数据范围与约定

对于所有数据，有：

• $2 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $0 \le a_i \le 10^9$
• $1 \le x \le N, \space 0 \le y \le 10^9$
• $1 \le l \le N, \space 1 \le l+2^k-1 \le N$