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 a1,a2,…,aN and Q operations. There are two types of operations.
- Modify operation: Given x,y, change ax to y.
- Query operation: Given L,R. Consider aL,aL+1,…,aR as coins with values aL,aL+1,…,aR, 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 a1,a2,…,aN.
Then, the following Q lines are the operations. Each operation must follow the following two formats:
- 1 x y: Modify operation.
- 2 L R: Query operation.
The meaning of the variable are stated in the problem description!
- 1≤N,Q,ai≤2×105
- 1≤x≤N
- 1≤y≤2×105
- 1≤L≤R≤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