题目描述

题意描述

给定一个数列 $a_1, a_2, \cdots, a_n$，你需要对这个序列进行如下的两种操作：

• $1$ $l$ $r$ — 对于任意的 $l \le i \le r$，将 $a_i$ 修改为 $a_i$ 的数位之和。
• $2$ $x$ — 输出 $a_x$ .

输入格式

第一行包括一个整数 $t$ ($1 \le t \le 1000$) ，为测试数据的组数。

每组测试数据的第一行包括两个整数 $n$，$q$ ($1 \le n, q \le 2 \times 10 ^ 5$)，其中 $n$ 是数列的长度，$q$ 是询问的个数。

每组测试数据的第二行包括 $n$ 整数，为 $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le 10 ^ 9$) 。

接下来的 $q$ 行包括以下两种形式的操作：

• $1$ $l$ $r$ ( $1 \leq l \leq r \leq n$ ) — 对于任意的 $l \le i \le r$，将 $a_i$ 修改为 $a_i$ 的数位之和。
• $2$ $x$ ( $1 \leq x \leq n$ ) — 输出 $a_x$。

每组测试数据包含至少一个操作二。

所有测试数据的 $n$ 的总和不会超过 $2 \times 10 ^ 5$。

所有测试数据的 $q$ 的总和不会超过 $2 \times 10 ^ 5$。

输出格式

对于每一组测试数据，按照输入给出的顺序输出操作二的答案。

样例

3
5 8
1 420 69 1434 2023
1 2 3
2 2
2 3
2 4
1 2 5
2 1
2 3
2 5
2 3
9999 1000
1 1 2
2 1
2 2
1 1
1
2 1

6
15
1434
1
6
7
36
1
1

样例说明

第一组测试数据的操作过程如下：

• 开始时，$a = [1, 420, 69, 1434, 2023]$。
• 对 $l=2$，$r=3$ 执行操作, 完成后 $a$ 变为 $[1, \textcolor{red}{6}, \textcolor{red}{15}, 1434, 2023]$。
• 询问 $x=2$ , $x=3$ 以及 $x=4$，输出 $6$，$15$ 以及 $1434$。
• 对 $l=2$ , $r=5$ 执行操作，完成后 $a$ 变为 $[1, \textcolor{red}{6}, \textcolor{red}{6}, \textcolor{red}{12}, \textcolor{red}{7}]$。
• 询问 $x=1$，$x=3$ 以及 $x=5$，输出 $1$，$6$ 以及 $7$。

来源

Codeforces 1791F，英文题名 Range Update Point Query。