Problem Description

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?

Input

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.

Output

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

Author

学军中学