Yuuki 是一位在麻将方面极具天赋的可爱高中生，她想出了一个很酷的问题。问题如下：

给定一个包含 $N$ 个整数的序列 $a_1, a_2, \dots, a_N$ 以及 $Q$ 次操作。操作分为两种类型：

• 修改操作：给定 $x, y$，将 $a_x$ 修改为 $y$。
• 查询操作：给定 $L, R$。考虑硬币序列 $a_L, a_{L + 1}, \dots, a_R$，请找出最小的正整数 $yuuki$，使得无法从这些硬币中选出一个子集，满足子集内硬币数值之和等于 $yuuki$。

输入格式

第一行包含两个整数 $N, Q$，分别表示序列的长度和操作次数。

接下来一行包含 $N$ 个空格分隔的整数 $a_1, a_2, \dots, a_N$。

接下来的 $Q$ 行描述操作。每种操作遵循以下两种格式之一：

1. $1 \ x \ y$：修改操作。
2. $2 \ L \ R$：查询操作。

变量含义如题目描述所述！

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

输出格式

对于每次查询操作，输出对应的 $yuuki$ 值，每行一个。

样例

样例输入 1

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

样例输出 1

2
1
7
6
2