Problem Background

Translated from Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection) D1T1. $\texttt{2s,1G}$.

Two pharaonic yellow lines turned into an eye...

Problem Description

Jusuf has $N$ cards, numbered from $1$ to $N$ from left to right. Each card has a strength $p_i$. As Jusuf is about to participate in a competition, he wants to imagine battles in his mind. Sometimes, he also changes the strength values of the cards. Jusuf will perform a total of $Q$ operations, each of which is one of the following types:

1. 1 i r: Jusuf sets the strength of the card at position $i$ to $r$, i.e., $p_i \gets r$.

2. 2 l k: Jusuf imagines a battle. This battle uses the cards from the $l$-th to the $(l + 2^k - 1)$-th, a total of $2^k$ cards.

   The battle will proceed for $k$ rounds. In each round, Jusuf pairs the $(2i-1)$-th and $2i$-th cards (e.g., the 1st and 2nd cards are paired). For each pair, Jusuf compares their strengths. Let the strengths of the two cards be $A$ and $B$, respectively. The card with the greater strength wins, and its strength becomes $|A - B|$, while the other card is removed. Specifically, if $A = B$, the result of the battle is indeterminate, and a random card wins, with its strength becoming $0$. Note that after $k$ rounds, only one card remains, and Jusuf wants to know its strength.

Since Jusuf is only imagining the battles, the actual number of cards and their strengths $p_i$ do not change.

Input Format

The first line contains two positive integers $N$ and $Q$, as described in the problem statement.

The second line contains $N$ integers, where the $i$-th integer represents $p_i$.

The next $Q$ lines each contain three positive integers, describing an operation.

Output Format

For each operation of type $2$, output a single line containing an integer representing the strength of the remaining card.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2
6

Sample Input #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

Sample Output #2

0
3
93

Sample Input #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

Sample Output #3

2
1
0

Notes/Hints

Sample Explanation

For the first query in Sample 1, the process is:

$$(\bold{\textcolor{red}{4}},8,\bold{\textcolor{red}{2}},0)\to (\bold{\textcolor{red}{4}},2)\to(2)$$

For the second query in Sample 1, the process is:

$$ (\bold{\textcolor{red}{8}},2)\to(6)$$

Data Range

For $100\%$ of the data, the following constraints are guaranteed:

• $2 \le N \le 200,000$, $1 \le Q \le 200,000$;
• $0 \le p_i \le 10^9$;
• $1 \le i \le N$, $0 \le r \le 10^9$;
• $1 \le l \le N$, $1 \le l + 2^k - 1 \le N$.

见题面 Input 部分

见题面 Output 部分