题目描述

给定一个数组 $a_1,a_2,…,a_n$，您需要处理总共 $q$ 个指令：

1 $l\ r$ 对于 $l≤i≤r$ 的每个索引 $i$，将 $a_i$ 的值更新为 $a_i$ 的各位数字之和。

2 $x$ 输出 $a_x$ 的值。

输入格式

输入的第一行包含一个整数 $t(1≤t≤1000)$ 代表测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $q(1≤n,q≤2×10^5)$，分别是数组的大小和查询的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,…,a_n(1≤a_i≤10^9)$。

每个测试用例的接下来 $q$ 行有两种指令：

1 $l\ r(1≤l≤r≤n)$ 表示对于 $l≤i≤r$ 的每个索引 $i$，应将 $a_i$ 的值更新为其各位数字的和。

2 $x(1≤x≤n)$ 表示你应该输出 $a_x$。

至少有一个输出操作。

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

所有测试用例的 $q$ 之和不超过 $2×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$ 区间进行操作，得出 $[1,6,15,1434,2023]$。

查询 $x=2,x=3,x=4$ 以及输出 $6,15,1434$。

对 $l=2,r=5$ 区间进行操作，得出 $[1,6,6,12,7]$。

我们将查询 $x=1,x=3,x=5$，以及输出 $1,6,7$。