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. The power of the $i$-th card is $p_i$. Since Jusuf is about to take part in a contest, he wants to imagine battles in his mind. Sometimes, he also changes the power values of the cards. In total, Jusuf will perform $Q$ operations, and each operation is one of the following two types:

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

2. 2 l k: Jusuf imagines a battle in his mind. This battle uses $2^k$ cards from the $l$-th card to the $(l + 2^k - 1)$-th card, i.e. cards $l,l+1,\cdots,l + 2^k − 1$.

   The battle will last for $k$ rounds. In each round, Jusuf groups the $(2i-1)$-th and the $2i$-th cards together (for example, the $1$-st and the $2$-nd cards form a group).

   For each group of cards, Jusuf compares their powers. Suppose the powers of the two cards are $A$ and $B$. The card with the larger power wins, and the winning card’s power becomes $|A − B|$, while the other card is removed. In particular, if $A=B$, then the result of this battle cannot be determined: one card will win at random, and its power becomes $0$.

   Note that after $k$ rounds, only one card will remain. Jusuf wants to know the power of this remaining card.

Since Jusuf is only imagining the battle, the number of cards will not actually change, and $p_i$ will not change either.

Input Format

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

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

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

Output Format

For each operation of type $2$, output one integer per line, representing the required power.

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

2
6

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

0
3
93

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

2
1
0

Hint

Sample Explanation

For the first query of sample $1$, we have:

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

For the second query of sample $1$, we have:

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

Constraints

For $100\%$ of the testdata, it is guaranteed that:

• $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$。

Subtask ID	Points	Constraints
$1$	$11$	$N, Q \leq 1000$
$2$	$13$	$N=2^k$
$3$	$16$	$0\le p_i,r\le 1$
$4$	$17$	No modification operations
$5$	$43$	No additional constraints

Translated by ChatGPT 5