Rikka with Sequence

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Yuta has an array A with n numbers. Then he makes m operations on it.

There are three type of operations:

1 l r x : For each i in [l,r], change A[i] to A[i]+x
2 l r : For each i in [l,r], change A[i] to $\lfloor \sqrt A[i] \rfloor$
3 l r : Yuta wants Rikka to sum up A[i] for all i in [l,r]

It is too difficult for Rikka. Can you help her?

The first line contains a number t(1<=t<=100), the number of the testcases. And there are no more than 5 testcases with n>1000.

For each testcase, the first line contains two numbers n,m(1<=n,m<=100000). The second line contains n numbers A[1]~A[n]. Then m lines follow, each line describe an operation.

It is guaranteed that 1<=A[i],x<=100000.

For each operation of type 3, print a lines contains one number -- the answer of the query.

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

5
6

学军中学

2016 Multi-University Training Contest 8