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

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

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

见题面 Input 部分

见题面 Output 部分

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$.