CF1791F.Range Update Point Query

Given an array $a_1, a_2, \dots, a_n$ , you need to handle a total of $q$ updates and queries of two types:

• $1$ $l$ $r$ — for each index $i$ with $l \leq i \leq r$ , update the value of $a_i$ to the sum of the digits of $a_i$ .
• $2$ $x$ — output $a_x$ .

The first line of the input contains an integer $t$ ( $1 \leq t \leq 1000$ ) — the number of testcases.

The first line of each test case contains two integers $n$ and $q$ ( $1 \le n, q \le 2 \cdot 10^5$ ) — the size of the array and the number of queries, respectively.

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

The next $q$ lines of each test case are of two forms:

• $1$ $l$ $r$ ( $1 \leq l \leq r \leq n$ ) — it means, for each index $i$ with $l \leq i \leq r$ , you should update the value of $a_i$ to the sum of its digits.
• $2$ $x$ ( $1 \leq x \leq n$ ) — it means you should output $a_x$ .

There is at least one query of the second type.

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .

The sum of $q$ over all test cases does not exceed $2 \cdot 10^5$ .

For each test case, output the answers of queries of the second type, in the order they are given.

In the first test case, the following process occurs:

• Initially, $a = [1, 420, 69, 1434, 2023]$ .
• The operation is performed for $l=2$ , $r=3$ , yielding $[1, \textcolor{red}{6}, \textcolor{red}{15}, 1434, 2023]$ .
• We are queried for $x=2$ , $x=3$ , and $x=4$ , and output $6$ , $15$ , and $1434$ .
• The operation is performed for $l=2$ , $r=5$ , yielding $[1, \textcolor{red}{6}, \textcolor{red}{6}, \textcolor{red}{12}, \textcolor{red}{7}]$ .
• We are queried for $x=1$ , $x=3$ , and $x=5$ , and output $1$ , $6$ , and $7$ .