让我们按以下方式定义平衡多重集。以十进制表示形式写下多重集所有元素的总和。对于该数字的每个位置,检查多重集是否包含至少一个元素,使得该元素的数字与该位置处的总和的数字相同。如果每个位置都成立,则多重集是平衡的。不然就不平衡了。
例如,多重集 $$$\{20, 300, 10001\}$$$ 是平衡的,多重集 $$$\{20, 310, 10001\}$$$ 是不平衡的:
红色数字标记元素以及这些元素与总和具有相同数字的位置。第一个多重集合的总和是$$$10321$$$,每个位置都有所需的数字。第二个多重集的总和是 $$$10331$$$ 并且倒数第二个数字没有出现在任何数字中,从而使多重集不平衡。
给定一个数组 $$$a_1, a_2, \dots, a_n$$$,由 $$$n$$$ 整数组成。
系统会要求您对其执行一些查询。查询可以有两种类型:
- $$$1~i~x$$$ — 将 $$$a_i$$$ 替换为值 $$$x$$$;
- $$$2~l~r$$$ — 找到数字 $$$a_l, a_{l + 1}, \dots, a_r$$$ 的多重集的不平衡子集,其总和最小,或者报告不存在不平衡子集。
请注意,空多重集是平衡的。
对于第二类型的每个查询,打印不平衡子集的最低总和。如果不存在不平衡子集,则打印 -1。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — 分别是数组中的元素数量和查询数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i < 10^9$$$)。
以下 $$$m$$$ 行中的每一行都包含以下两种类型之一的查询:
- $$$1~i~x$$$ ($$$1 \le i \le n$$$, $$$1 \le x < 10^9$$$) — 将 $$$a_i$$$ 替换为值 $$$x$$$;
- $$$2~l~r$$$ ($$$1 \le l \le r \le n$$$) — 找到数字 $$$a_l, a_{l + 1}, \dots, a_r$$$ 的多重集合中总和最小的不平衡子集,或者报告不存在不平衡子集。
保证至少有一个第二类型的查询。
输出
对于第二类型的每个查询,打印不平衡子集的最低总和。如果不存在不平衡子集,则打印 -1。
示例
输入 #1
4 5 300 10001 20 20 2 1 3 1 1 310 2 1 3 2 3 3 2 3 4
输出 #1
-1 330 -1 40
注意
多重集 $$$\{20, 300, 10001\}$$$ 的所有子集都是平衡的,因此答案为 -1。
第三个查询中可能的不平衡子集是 $$$\{20, 310\}$$$ 和 $$$\{20, 310, 10001\}$$$。最小的总和是 $$$\{20, 310\}$$$。请注意,系统会要求您选择一个子集,而不是子段,因此所选元素可能不会在数组中相邻。
第四个查询仅包含空子集和子集$$$\{20\}$$$。两者都是平衡的。
最后一个查询包括空子集和子集 $$$\{20\}$$$、$$$\{20\}$$$ 和 $$$\{20, 20\}$$$。只有$$$\{20, 20\}$$$是不平衡的,它的总和是$$$40$$$。请注意,系统会要求您选择一个多重集,因此它可能包含相同的元素。