Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

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?

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 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.

提交代码