Bob 的数学真的很差。他甚至不知道在加法运算中“进位”是如何工作的。在他的世界里，“加法”运算是这样执行的：$9 + 5 = 4$，$99 + 99 = 88$，$5876 + 5576 = 342$，$5555 + 5555 = 0$，$1503 + 2503 = 3006$，$512 + 1314 = 1826$。他的数学真是太差了，他甚至可能成为出题人。真是悲剧。在他的世界里，有一种名为“Wish”的数据结构。让我们看看它是如何工作的：

• 最初，会有一个数字列表来初始化该数据结构。初始化完成后，游戏开始：

• 你可以向他的数据结构中添加一个数字。 Add x

• 你可以将数据结构中的所有数字除以 $10$。（注意：这是整数除法，例如，$9/10 = 0$，$99/10 = 9$，$5876/10 = 587$） Shift

• 你可以查询给定 $x$ 与他数据结构中的任意数字进行“加法”运算后的最大结果。 Query x

• 你可以查询数据结构中在 $L$ 到 $R$（包含 $L$ 和 $R$）之间的数字的“和”（按照他那糟糕的数学）。这意味着，你需要找到他数据结构中所有满足 $L \le x \le R$ 的数字 $x$，并依次进行“加法”运算以得到“和”。 Sum L R

你能帮帮天真的 Bob 实现“Wish”数据结构吗？

输入格式

最开始有一个数字 $T$ 表示测试用例的数量。($1 \le T \le 100$)

对于每个测试用例： 第一行包含两个整数 $N$ 和 $M$，分别表示初始数字的数量和操作的数量。($1 \le N \le 10,000$ 且 $1 \le M \le 10,000$) 第二行包含 $N$ 个整数，表示初始数字 $a_i$。($0 \le a_i \le 2 \times 10^9$) 接下来的 $M$ 行遵循上述 #1 到 #4 的操作格式。 对于这些操作，$0 \le L \le R \le 2 \times 10^9$，$0 \le x \le 2 \times 10^9$。

输出格式

对于每个测试用例，输出一行包含“Case #x:”，其中 $x$ 是测试用例编号（从 $1$ 开始）。对于每个 Query 和 Sum 操作，输出答案。

样例

输入 1

1
4 5
1 2 88 29
Add 44
Query 71
Shift
Sum 0 10
Query 91

输出 1

Case #1:
90
4
99

说明

对于样例 1：

• 初始：$[1, 2, 29, 88]$
• Add 44：$[1, 2, 29, 88, 44]$
• Query 71：$29 + 71 = 90$；$88 + 71 = 59$；$44 + 71 = 15$
• Shift：$[0, 0, 2, 8, 4]$
• Sum 0 10：$0 + 0 + 2 + 8 + 4 = 4$
• Query 91：$91 + 8 = 99$