Description:
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$$$.
Input Format:
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$$$.
Output Format:
For each test case, output the answers of queries of the second type, in the order they are given.
Note:
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, \color{red}{6}, \color{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, \color{red}{6}, \color{red}{6}, \color{red}{12}, \color{red}{7}]$$$.
- We are queried for $$$x=1$$$, $$$x=3$$$, and $$$x=5$$$, and output $$$1$$$, $$$6$$$, and $$$7$$$.