Young Jusuf has $N$ cards in his deck, arranged from left to right from $1$ to $N$. Each card has a strength which we will denote by $p_i$. Jusuf wants to prepare for an upcoming tournament, so he wants to test battles between his cards and swap cards in his deck with various other cards he received as a gift from his grandfather. In total, Jusuf will perform $Q$ queries, each of which will be one of the following two types:

• 1 i r - denotes a query in which Jusuf replaces the card at position $i$ with a new card of strength $r$.
• 2 l k - Jusuf will imagine an imaginary battle with $2^k$ cards, starting from the $l$-th and ending at the $l + 2^k - 1$-th, and shout "It's time to duel!". The battle will take place in $k$ steps. In each step, Jusuf will observe pairs of adjacent cards (the first and second, the third and fourth, etc.) and compare their strengths; let them be $A$ and $B$ in a pair. The card with the greater strength will win, and its new strength will be $|A - B|$ (whichever card won). If the cards have equal strength, the battle will be uncertain, a random card will win, and its strength will be $0$. The card that lost does not participate in the remaining rounds. Note that after $k$ such steps, exactly one card will remain. Jusuf is interested in its strength!

Input

The first line contains the natural numbers $N$ and $Q$.

The next line contains $N$ numbers $p_i$ ($0 \le p_i \le 10^9$) which denote the strengths of the cards.

The next $Q$ lines contain descriptions of the queries that correspond to the problem text.

For each query of type 1, $1 \le i \le N$ and $0 \le r \le 10^9$ hold.

For each query of type 2, $1 \le l \le N$ and $1 \le l + 2^k - 1 \le N$ hold.

Output

For each query of type 2, it is necessary to print the strength of the final card after all $k$ steps.

Subtasks

In all subtasks, $2 \le N \le 200\,000$ and $1 \le Q \le 200\,000$ hold.

Examples

Input 1

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

Output 1

2
6

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

Output 2

0
3
93

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

Output 3

2
1
0

Note

Explanation of the first example:

In the first query, the cards will change during the steps as follows: $(4, 8, 2, 0) \to (4, 2) \to (2)$

In the third query, the cards will change during the steps as follows: $(8, 2) \to (6)$