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

给定一个数组 $a_1, a_2, \dots, a_n$，你需要处理总共 $q$ 个更新与查询操作，操作分为两类：

• $1$ $l$ $r$ — 对每个满足 $l \leq i \leq r$ 的下标 $i$，将 $a_i$ 的值更新为 $a_i$ 的各位数字之和。
• $2$ $x$ — 输出 $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$.

输入的第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 2 \cdot 10^5$），分别表示数组的大小和查询的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$）。

每个测试用例接下来的 $q$ 行为以下两种形式之一：

• $1$ $l$ $r$（$1 \leq l \leq r \leq n$）—— 表示对每个满足 $l \leq i \leq r$ 的下标 $i$，将 $a_i$ 更新为其各位数字之和；
• $2$ $x$（$1 \leq x \leq n$）—— 表示输出 $a_x$ 的值。

保证每个测试用例中至少存在一个类型为 2 的查询。

所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

所有测试用例的 $q$ 之和不超过 $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, \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$.

在第一个测试用例中，发生如下过程：

• 初始时，$a = [1, 420, 69, 1434, 2023]$。
• 对 $l=2$、$r=3$ 执行操作，得到 $[1, \color{red}{6}, \color{red}{15}, 1434, 2023]$。
• 查询 $x=2$、$x=3$ 和 $x=4$，输出结果为 $6$、$15$ 和 $1434$。
• 对 $l=2$、$r=5$ 执行操作，得到 $[1, \color{red}{6}, \color{red}{6}, \color{red}{12}, \color{red}{7}]$。
• 查询 $x=1$、$x=3$ 和 $x=5$，输出结果为 $1$、$6$ 和 $7$。