该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

33DAI 有一个长度为 $n$ 的整数数列 $a_1, a_2, \dots, a_n$（下标从 $1$ 开始），需要按顺序处理 $q$ 次操作，操作有两种：

• 1 l r：对所有满足 $l \le i \le r$ 的下标 $i$，把 $a_i$ 修改为 $a_i$ 的十进制数位之和；
• 2 x：输出当前的 $a_x$。

数位之和指各位数字相加，例如 $1434$ 的数位之和是 $1 + 4 + 3 + 4 = 12$。执行操作一后 $a_i$ 一定不小于 $1$。

输入格式

从文件 digit.in 读入数据。

输入的第一行包含一个正整数 $t$，表示测试数据组数。

接下来依次给出 $t$ 组数据，每组数据的格式为：

第一行包含两个整数 $n$ 与 $q$，分别表示数列长度与操作次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$。

接下来 $q$ 行，每行描述一次操作，格式为下列两种之一：

• 1 l r：含义见题目描述，保证 $1 \le l \le r \le n$；
• 2 x：含义见题目描述，保证 $1 \le x \le n$。

输出格式

输出到文件 digit.out。

对于每次 2 x 操作，按这些操作在输入中出现的顺序输出一行一个整数，表示当时的 $a_x$。

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

样例 1 解释

第一组数据的过程：

• 初始 $a = [1, 420, 69, 1434, 2023]$；
• 执行 1 2 3：$420 \to 6$，$69 \to 15$，得到 $a = [1, 6, 15, 1434, 2023]$；
• 依次查询 $x = 2, 3, 4$，输出 $6, 15, 1434$；
• 执行 1 2 5：$6 \to 6$，$15 \to 6$，$1434 \to 12$，$2023 \to 7$， 得到 $a = [1, 6, 6, 12, 7]$；
• 依次查询 $x = 1, 3, 5$，输出 $1, 6, 7$。

第二组数据：$a = [9999, 1000]$，执行 1 1 2 后 $9999 \to 36$、$1000 \to 1$； 随后两次询问 2 1、2 2 依次输出 $36$ 与 $1$。

第三组数据的 $n = 1$，$a_1 = 1$，唯一的询问 2 1 输出 $1$。

样例 2

见 digit2.in 与 digit2.ans。

样例 3

见 digit3.in 与 digit3.ans。

数据范围

对于所有测试数据，保证：

• $1 \le t \le 1000$；
• $1 \le n, q \le 2 \times 10^5$；
• $1 \le a_i \le 10^9$；
• 每组数据中至少有一次 2 x 操作；
• 单个测试文件中所有测试用例的 $n$ 之和不超过 $2 \times 10^5$；
• 单个测试文件中所有测试用例的 $q$ 之和不超过 $2 \times 10^5$。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。