给你一个包含 $n$ 个整数的数组 $a$。共有三种类型的操作：

• 1 l r x：对于 $[l, r]$ 区间内的每个 $i$，将 $a_i$ 修改为 $a_i + x$；
• 2 l r：对于 $[l, r]$ 区间内的每个 $i$，将 $a_i$ 修改为 $\lfloor \sqrt{a_i} \rfloor$；
• 3 l r：求 $[l, r]$ 区间内所有 $i$ 的 $a_i$ 之和，并输出答案。

你的目标是处理这些操作，并输出所有类型 3 操作的答案。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^5$)。

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

接下来的 $q$ 行，每行描述一个操作。

保证 $1 \le a_i, x \le 10^5$，$1 \le l \le r \le n$。

输出格式

对于每个类型 3 的操作，输出一行，包含所求的和。

样例

输入样例 1

5 5
1 2 3 4 5
1 3 5 2
2 1 4
3 2 4
2 3 5
3 1 5

输出样例 1

5
6