I-Sum Queries?

题目描述

我们这样定义一个“平衡多重集”：将多重集所有元素的和写成十进制sum表示。对于该数字的每一位，检查多重集中是否存在至少一个元素x，使得sum在对应位置上的数字与x在该位置上的数字相同。如果每一位都满足这个条件，则该多重集是平衡的；否则就是不平衡的。

例如，多重集 $\{20, 300, 10001\}$ 是平衡的，而多重集 $\{20, 310, 10001\}$ 是不平衡的：

红色数字标记了那些元素及其在和中与之相同的数字位置。第一个多重集的和为 $10321$，每一位都存在对应的元素数字。第二个多重集的和为 $10331$，倒数第二位的数字没有在任何元素中出现，因此该多重集是不平衡的。

现在给定一个由 $n$ 个整数构成的数组 $a_1, a_2, \dots, a_n$。

你需要对其进行若干次操作，操作有两种类型：

• $1~i~x$ —— 将 $a_i$ 替换为 $x$；
• $2~l~r$ —— 在多重集 $a_l, a_{l+1}, \dots, a_r$ 的所有子集（可以包含重复元素）中，找出和最小的不平衡子集，并输出其和。如果不存在不平衡子集，则输出 $-1$。

注意，空多重集是平衡的。

对于每个第二类操作，输出不平衡子集的最小和。如果不存在不平衡子集，则输出 $-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

输入 #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$。注意你需要选择的是多重集，因此可以包含相同的元素。