我们都喜欢没有背景故事的题目，不是吗？！这里还有一道。

在这个问题中，给定一个包含 $N$ 个整数的数组 $a_1, a_2, \dots, a_N$。随后有 $Q$ 次查询，每次查询属于以下类型之一：

1. 对于每个 $L \le i \le R$ 的整数 $a_i$，将其替换为 $\lfloor \sqrt{a_i} \rfloor$。其中 $\sqrt{a}$ 是 $a$ 的平方根，$\lfloor b \rfloor$ 是 $b$ 去掉小数点后所有数字得到的整数。
2. 输出所有满足 $L \le i \le R$ 的整数 $a_i$ 的和。
3. 将 $x$ 加到每个满足 $L \le i \le R$ 的整数 $a_i$ 上。

输入格式

程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。接下来是 $T$ 个测试用例。

每个测试用例的第一行包含两个用空格分隔的整数 $N$ ($1 \le N \le 10^5$) 和 $Q$ ($1 \le Q \le 20,000$)，分别表示数组中整数的个数和查询的数量。

接下来一行包含 $N$ 个用空格分隔的整数，表示数组中的初始整数 $a_1, a_2, \dots, a_N$ ($1 \le a_i \le 10^6$)。

接下来有 $Q$ 行，每行将是以下格式之一 ($1 \le L \le R \le N$) 且 ($1 \le x \le 10^6$)：

第一类查询：1 L R 第二类查询：2 L R 第三类查询：3 L R x

输出格式

对于每个第二类查询，在一行中输出相应的答案。

样例

样例输入 1

1
10 7
1 5 123 53 12 2901 12 1234 657 3419
2 3 7
3 5 8 1
1 2 4
3 1 6 1000
2 1 10
2 2 8
1 3 5

样例输出 1

3101
14260
9183