给出一个长度为 n 的整数序列 A[1..n]，有三种操作： 
1 l r x :  把[l, r]区间的每个数都加上 x 
2 l r :  把[l, r]  区间每个 A[i]变为sqrt(a[i])的整数部分
3 l r :  求[l, r]  区间所有数的和 
其中 l 和 r 和 x 都代表一个整数 

第一行一个 T，表示数据组数。 
对于每组数据 
Line1：两个数 n m，表示整数序列长度和操作数 
Line2：n 个数，表示 A[1..n] 
Line3…Line3+m-1：每行一个询问，对于第三种询问，请输出答案。 
对于每一种询问，先给出操作的编号，再给出相应的操作，编号与题目描述对应。 
数据约定： 
1<=T<=5 
n,m <= 100000 
1<= A[i], x<=100000 

对于第三种询问，输出答案。每个答案占一行。 

15 51 2 3 4 51 3 5 22 1 43 2 42 3 53 1 5

56