CF794F.Leha and security system

Bankopolis, the city you already know, finally got a new bank opened! Unfortunately, its security system is not yet working fine... Meanwhile hacker Leha arrived in Bankopolis and decided to test the system!

Bank has n cells for clients' money. A sequence from n numbers _a_1, _a_2, ..., a__n describes the amount of money each client has. Leha wants to make requests to the database of the bank, finding out the total amount of money on some subsegments of the sequence and changing values of the sequence on some subsegments. Using a bug in the system, Leha can requests two types of queries to the database:

• 1 l r x y denoting that Leha changes each digit x to digit y in each element of sequence a__i, for which l ≤ i ≤ r is holds. For example, if we change in number 11984381 digit 8 to 4, we get 11944341. It's worth noting that Leha, in order to stay in the shadow, never changes digits in the database to 0, i.e. y ≠ 0.
• 2 l r denoting that Leha asks to calculate and print the sum of such elements of sequence a__i, for which l ≤ i ≤ r holds.

As Leha is a white-hat hacker, he don't want to test this vulnerability on a real database. You are to write a similar database for Leha to test.

Bankopolis——这座你早已熟知的城市，终于迎来了一家新银行的开业！不幸的是，其安全系统尚未完全正常运行……与此同时，黑客 Leha 抵达了 Bankopolis，并决定对这套系统进行测试！

该银行拥有 $n$ 个用于存放客户资金的“单元格”。一个由 $n$ 个数字组成的序列 $a_1,\,a_2,\,\dots,\,a_n$ 描述了每位客户所拥有的资金数额。Leha 希望向银行数据库发出若干请求，以查询某段子区间内资金总额，以及修改某段子区间内序列的值。借助系统中的一处漏洞，Leha 可向数据库发起以下两类查询：

• 1 l r x y：表示 Leha 将对所有满足 $l \le i \le r$ 的序列元素 $a_i$，将其十进制表示中每一个数字 $x$ 替换为数字 $y$。例如，若将数字 11984381 中的所有数字 8 替换为 4，则结果为 11944341。需特别注意的是，为保持隐匿，Leha 绝不会将任何数字替换为 0，即恒有 $y \neq 0$。
• 2 l r：表示 Leha 请求计算并输出所有满足 $l \le i \le r$ 的序列元素 $a_i$ 的总和。

由于 Leha 是一名白帽黑客，他并不打算在真实数据库上测试此漏洞。你需要为 Leha 编写一个功能类似的模拟数据库以供其测试。

The first line of input contains two integers n and q (1 ≤ n ≤ 105, 1 ≤ q ≤ 105) denoting amount of cells in the bank and total amount of queries respectively.

The following line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i < 109) denoting the amount of money in each cell initially. These integers do not contain leading zeros.

Each of the following q lines has one of the formats:

• 1 l r x y (1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 9, 1 ≤ y ≤ 9), denoting Leha asks to change each digit x on digit y for each element a__i of the sequence for which l ≤ i ≤ r holds;
• 2 l r (1 ≤ l ≤ r ≤ n), denoting you have to calculate and print the sum of elements a__i for which l ≤ i ≤ r holds.

输入的第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 10^5$，$1 \leq q \leq 10^5$），分别表示银行中单元格的数量以及查询的总次数。

接下来的一行包含 $n$ 个整数 $a_1,\,a_2,\,\dots,\,a_n$（$1 \leq a_i < 10^9$），表示每个单元格初始所存的钱数。这些整数不含前导零。

接下来的 $q$ 行中，每行属于以下两种格式之一：

• 1 l r x y（$1 \leq l \leq r \leq n$，$0 \leq x \leq 9$，$1 \leq y \leq 9$），表示 Leha 要求对所有满足 $l \leq i \leq r$ 的序列元素 $a_i$，将其十进制表示中每一个数字 $x$ 替换为数字 $y$；
• 2 l r（$1 \leq l \leq r \leq n$），表示你需要计算并输出所有满足 $l \leq i \leq r$ 的元素 $a_i$ 的和。

For each second type query print a single number denoting the required sum.

对于每个第二类查询，输出一个数字，表示所要求的和。

Let's look at the example testcase.

Initially the sequence is [38, 43, 4, 12, 70].

After the first change each digit equal to 4 becomes 8 for each element with index in interval [1; 3]. Thus, the new sequence is [38, 83, 8, 12, 70].

The answer for the first sum's query is the sum in the interval [2; 4], which equal 83 + 8 + 12 = 103, so the answer to this query is 103.

The sequence becomes [38, 83, 8, 12, 78] after the second change and [38, 73, 7, 12, 77] after the third.

The answer for the second sum's query is 38 + 73 + 7 + 12 + 77 = 207.

我们来看一下样例测试用例。

初始序列为

38,\ 43,\ 4,\ 12,\ 70$$。 第一次修改将区间 $[1; 3]$ 内每个元素中所有等于 $4$ 的数字替换为 $8$。因此，新序列为 $$38,\ 83,\ 8,\ 12,\ 70$$。 第一个求和查询的区间为 $[2; 4]$，其和为 $83 + 8 + 12 = 103$，故该查询的答案为 $103$。 第二次修改后序列变为 $$38,\ 83,\ 8,\ 12,\ 78$$，第三次修改后变为 $$38,\ 73,\ 7,\ 12,\ 77$$。 第二个求和查询的答案为 $38 + 73 + 7 + 12 + 77 = 207$。