Yuuki, a cute senior high school student with excellent talent in mahjong, comes up with a cool problem. The problem goes as follows:

Given a sequence with $N$ integers $a_1, a_2, \dots, a_N$ and $Q$ operations. There are two types of operations.

• Modify operation: Given $x, y$, change $a_x$ to $y$.
• Query operation: Given $L, R$. Consider $a_L, a_{L + 1}, \dots, a_{R}$ as coins with values $a_L, a_{L + 1}, \dots, a_R$, please find out the minimum number $yuuki$, such that it is impossible to choose a subset of the coins stated before, such that the sum of their values is $yuuki$.

Input

The first line of the input contains two integers $N, Q$ denotes the length of the sequence and the number of operations.

Then, there are $N$ space-separated integers $a_1, a_2, \dots, a_N$.

Then, the following $Q$ lines are the operations. Each operation must follow the following two formats:

1. $1 \ x \ y$: Modify operation.
2. $2 \ L \ R$: Query operation.

The meaning of the variable are stated in the problem description!

• $1 \le N, Q, a_i \le 2 \times 10^5$
• $1 \le x \le N$
• $1 \le y \le 2 \times 10^5$
• $1 \le L \le R \le N$

Output

For each query operation, output the corresponding $yuuki$ value in one line.

Sample Input

3 7
1 3 2
2 1 1
2 2 2
2 1 3
1 3 1
2 1 3
1 1 5
2 1 3

Sample Output

2
1
7
6
2