English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
For each second type query print a single number denoting the required sum.
[samples]
## Note
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.
你已经熟知的银行城 Bankopolis 终于新开了一家银行！可惜它的安全系统尚未完善……与此同时，黑客 Leha 抵达 Bankopolis，决定测试该系统！
银行有 #cf_span[n] 个存放客户资金的单元格。一个由 #cf_span[n] 个数字组成的序列 #cf_span[a1, a2, ..., an] 描述了每个客户拥有的金额。Leha 希望向银行数据库发送请求，查询序列某些子段的总金额，并修改序列某些子段的值。利用系统中的一个漏洞，Leha 可以向数据库发送两种类型的查询：
由于 Leha 是一名白帽黑客，他不希望在真实数据库上测试此漏洞。你需要为 Leha 编写一个类似的数据库以供测试。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n ≤ 10^5]，#cf_span[1 ≤ q ≤ 10^5]），分别表示银行中的单元格数量和查询总数。
接下来的一行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai < 10^9]），表示每个单元格初始的金额。这些整数不包含前导零。
接下来的 #cf_span[q] 行每行均为以下格式之一：
对于每个第二类查询，请输出一个表示所需和的数字。
让我们来看一个示例测试用例。
初始序列为 #cf_span[[38, 43, 4, 12, 70]]。
第一次修改后，区间 #cf_span[[1; 3]] 内每个等于 #cf_span[4] 的数字变为 #cf_span[8]。因此，新序列为 #cf_span[[38, 83, 8, 12, 70]]。
第一个求和查询的答案是区间 #cf_span[[2; 4]] 的和，即 #cf_span[83 + 8 + 12 = 103]，因此该查询的答案为 #cf_span[103]。
第二次修改后序列变为 #cf_span[[38, 83, 8, 12, 78]]，第三次修改后变为 #cf_span[[38, 73, 7, 12, 77]]。
第二个求和查询的答案为 #cf_span[38 + 73 + 7 + 12 + 77 = 207]。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n ≤ 10^5]，#cf_span[1 ≤ q ≤ 10^5]），分别表示银行中的单元格数量和查询总数。接下来的一行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai < 10^9]），表示每个单元格初始的金额。这些整数不包含前导零。接下来的 #cf_span[q] 行每行均为以下格式之一：
_1 l r x y_（#cf_span[1 ≤ l ≤ r ≤ n]，#cf_span[0 ≤ x ≤ 9]，#cf_span[1 ≤ y ≤ 9]），表示 Leha 要求将序列中满足 #cf_span[l ≤ i ≤ r] 的每个元素 #cf_span[ai] 中的数字 #cf_span[x] 替换为数字 #cf_span[y]；
_2 l r_（#cf_span[1 ≤ l ≤ r ≤ n]），表示你需要计算并输出满足 #cf_span[l ≤ i ≤ r] 的所有元素 #cf_span[ai] 的和。
## Output
对于每个第二类查询，请输出一个表示所需和的数字。
[samples]
## Note
让我们来看一个示例测试用例。
初始序列为 #cf_span[[38, 43, 4, 12, 70]]。第一次修改后，区间 #cf_span[[1; 3]] 内每个等于 #cf_span[4] 的数字变为 #cf_span[8]。因此，新序列为 #cf_span[[38, 83, 8, 12, 70]]。
第一个求和查询的答案是区间 #cf_span[[2; 4]] 的和，即 #cf_span[83 + 8 + 12 = 103]，因此该查询的答案为 #cf_span[103]。
第二次修改后序列变为 #cf_span[[38, 83, 8, 12, 78]]，第三次修改后变为 #cf_span[[38, 73, 7, 12, 77]]。
第二个求和查询的答案为 #cf_span[38 + 73 + 7 + 12 + 77 = 207]。
**Definitions**
Let $ n, q \in \mathbb{Z}^+ $ denote the number of cells and number of queries, respectively.
Let $ A = (a_1, a_2, \dots, a_n) $ be the initial sequence of integers, where $ a_i \in \mathbb{Z} $ and $ 1 \leq a_i < 10^9 $.
Each query is one of two types:
- **Type 1 (Update)**: Given $ l, r, x, y $, for each index $ i \in [l, r] $, replace every digit $ x $ in $ a_i $ with digit $ y $.
- **Type 2 (Query)**: Given $ l, r $, compute $ \sum_{i=l}^{r} a_i $.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ 1 \leq q \leq 10^5 $
3. $ 1 \leq a_i < 10^9 $ for all $ i \in \{1, \dots, n\} $
4. For Type 1 queries: $ 1 \leq l \leq r \leq n $, $ 0 \leq x, y \leq 9 $
5. For Type 2 queries: $ 1 \leq l \leq r \leq n $
**Objective**
For each Type 2 query with parameters $ l, r $, output:
$$
\sum_{i=l}^{r} a_i
$$
where $ a_i $ is the current value of the $ i $-th cell after all prior updates.
API Response (JSON)
{
"problem": {
"name": "F. Leha and security system",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF794F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你已经熟知的银行城 Bankopolis 终于新开了一家银行！可惜它的安全系统尚未完善……与此同时，黑客 Leha 抵达 Bankopolis，决定测试该系统！\n\n银行有 #cf_span[n] 个存放客户资金的单元格。一个由 #cf_span[n] 个数字组成的序列 #cf_span[a1, a2, ..., an] 描述了每个客户拥有的金额。Leha 希望向银行数据库发送请求，查询序列某些子段...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the number of cells and number of queries, respectively. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the initial sequence of integers, where $ a_i \\i...",
"is_translate": false,
"language": "Formal"
}
]
}