CF1217E.Sum Queries?

Let's define a balanced multiset the following way. Write down the sum of all elements of the multiset in its decimal representation. For each position of that number check if the multiset includes at least one element such that the digit of the element and the digit of the sum at that position are the same. If that holds for every position, then the multiset is balanced. Otherwise it's unbalanced.

For example, multiset ${20, 300, 10001}$ is balanced and multiset ${20, 310, 10001}$ is unbalanced:

The red digits mark the elements and the positions for which these elements have the same digit as the sum. The sum of the first multiset is $10321$, every position has the digit required. The sum of the second multiset is $10331$ and the second-to-last digit doesn't appear in any number, thus making the multiset unbalanced.

You are given an array $a_1, a_2, \dots, a_n$, consisting of $n$ integers.

You are asked to perform some queries on it. The queries can be of two types:

• $1~i~x$ — replace $a_i$ with the value $x$;
• $2~l~r$ — find the unbalanced subset of the multiset of the numbers $a_l, a_{l + 1}, \dots, a_r$ with the minimum sum, or report that no unbalanced subset exists.

Note that the empty multiset is balanced.

For each query of the second type print the lowest sum of the unbalanced subset. Print -1 if no unbalanced subset exists.

我们定义一个“平衡多重集”如下：将该多重集中所有元素的和用十进制表示出来；对这个和的每一位数字，检查该多重集中是否至少存在一个元素，使得该元素在该数位上的数字与和在该数位上的数字相同。若该条件对每一位均成立，则称该多重集为平衡的；否则称为不平衡的。

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

图中红色数字标出了满足“元素在该数位上的数字等于总和在该数位上的数字”的元素及其对应数位。第一个多重集的和为 $10321$，每一位数字均能在至少一个元素的对应数位上找到；第二个多重集的和为 $10331$，其倒数第二位（十位）数字为 $3$，但在任意一个元素的十位上均未出现数字 $3$，因此该多重集不平衡。

给定一个由 $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$ 构成的多重集中，找出一个不平衡子集，使其元素之和最小；若不存在不平衡子集，则报告不存在。

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

对于每个类型 $2$ 的查询，请输出该不平衡子集的最小可能和；若不存在不平衡子集，则输出 $-1$。

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of elements in the array and the number of queries, respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \lt 10^9$).

Each of the following $m$ lines contains a query of one of two types:

• $1~i~x$ ($1 \le i \le n$, $1 \le x \lt 10^9$) — replace $a_i$ with the value $x$;
• $2~l~r$ ($1 \le l \le r \le n$) — find the unbalanced subset of the multiset of the numbers $a_l, a_{l + 1}, \dots, a_r$ with the lowest sum, or report that no unbalanced subset exists.

It is guaranteed that there is at least one query of the second type.

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2 \cdot 10^5$），分别表示数组中元素的个数以及查询的个数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \lt 10^9$）。

接下来的 $m$ 行，每行描述一个两种类型之一的查询：

• $1~i~x$（$1 \le i \le n$，$1 \le x \lt 10^9$）—— 将 $a_i$ 替换为值 $x$；
• $2~l~r$（$1 \le l \le r \le n$）—— 在多重集 $\{a_l, a_{l + 1}, \dots, a_r\}$ 中，找出和最小的非平衡子集；若不存在非平衡子集，则报告该情况。

保证至少存在一个第二类查询。

For each query of the second type print the lowest sum of the unbalanced subset. Print -1 if no unbalanced subset exists.

对于每个第二类查询，输出不平衡子集的最小和。如果不存在不平衡子集，则输出 $-1$。

All the subsets of multiset ${20, 300, 10001}$ are balanced, thus the answer is -1.

The possible unbalanced subsets in the third query are ${20, 310}$ and ${20, 310, 10001}$. The lowest sum one is ${20, 310}$. Note that you are asked to choose a subset, not a subsegment, thus the chosen elements might not be adjancent in the array.

The fourth query includes only the empty subset and subset ${20}$. Both of them are balanced.

The last query includes the empty subset and the subsets ${20}$, ${20}$ and ${20, 20}$. Only ${20, 20}$ is unbalanced, its sum is $40$. Note that you are asked to choose a multiset, thus it might include equal elements.

多重集 $\{20, 300, 10001\}$ 的所有子集均为平衡的，因此答案为 $-1$。

第三次查询中可能的非平衡子集为 $\{20, 310\}$ 和 $\{20, 310, 10001\}$。其中和最小的是 $\{20, 310\}$。注意：题目要求选择一个子集（subset），而非连续子数组（subsegment），因此所选元素在原数组中未必相邻。

第四次查询仅包含空子集和子集 $\{20\}$，二者均为平衡的。

最后一次查询包含空子集以及子集 $\{20\}$、$\{20\}$ 和 $\{20, 20\}$。其中仅 $\{20, 20\}$ 是非平衡的，其和为 $40$。注意：题目要求选择一个多重集（multiset），因此它可能包含相等的元素。