// 判断相同区间(lazy) 多校8 HDU 5828 Rikka with Sequence

 // 题意：三种操作，1增加值，2开根，3求和

 // 思路：这题与HDU 4027 和HDU 5634 差不多

 // 注意开根号的话，遇到极差等于1的，开根号以后有可能还是差1.如

 // 2 3 2 3。。。

 // 8 9 8 9。。。

 // 2 3 2 3。。。

 // 8 9 8 9。。。

 // 剩下就是遇到区间相等的话，就直接开根号不往下传

 #include <bits/stdc++.h>

 using namespace std;

 #define LL long long

 const int inf = 0x3f3f3f3f;

 const int MOD =;

 const int N =1e5+;

 #define clc(a,b) memset(a,b,sizeof(a))

 const double eps = 1e-;

 void fre(){freopen("in.txt","r",stdin);}

 void freout() {freopen("out.txt","w",stdout);}

 inline int read() {int x=,f=;char ch=getchar();while(ch>''||ch<'') {if(ch=='-') f=-;ch=getchar();}while(ch>=''&&ch<='') {x=x*+ch-'';ch=getchar();}return x*f;}

 int n,q;

 int a[N];

 struct node{

     int l,r,len;

     LL sum,lazy;

     LL mx,mn;

 }t[N<<];

 void pushup(int rt){

     t[rt].sum=t[rt<<].sum+t[rt<<|].sum;

     t[rt].mx=max(t[rt<<].mx,t[rt<<|].mx);

     t[rt].mn=min(t[rt<<|].mn,t[rt<<].mn);

 }

 void pushdown(int rt){

     if(t[rt].lazy){

         t[rt<<].lazy+=t[rt].lazy;

         t[rt<<].mx+=t[rt].lazy;

         t[rt<<].mn+=t[rt].lazy;

         t[rt<<].sum+=t[rt<<].len*t[rt].lazy;

         t[rt<<|].lazy+=t[rt].lazy;

         t[rt<<|].mx+=t[rt].lazy;

         t[rt<<|].mn+=t[rt].lazy;

         t[rt<<|].sum+=t[rt<<|].len*t[rt].lazy;

         t[rt].lazy=;

     }

 }

 void build(int rt,int l,int r){

     t[rt].l=l;

     t[rt].r=r;

     t[rt].lazy=;

     t[rt].mx=;

     t[rt].mn=inf;

     t[rt].len=r-l+;

     if(l==r){

        t[rt].sum=a[l],t[rt].mx=t[rt].mn=a[l];

        return;

     }

     int mid=(l+r)>>;

     build(rt<<,l,mid);

     build(rt<<|,mid+,r);

     pushup(rt);

 }

 void update1(int rt,int l,int r,int z){

     if(t[rt].l>=l&&t[rt].r<=r){

         t[rt].sum+=(LL)t[rt].len*z;

         t[rt].lazy+=z;

         t[rt].mn+=z;

         t[rt].mx+=z;

         return;

     }

     pushdown(rt);

     int mid=(t[rt].l+t[rt].r)>>;

     if(r<=mid) update1(rt<<,l,r,z);

     else if(l>mid) update1(rt<<|,l,r,z);

     else {

         update1(rt<<,l,mid,z);

         update1(rt<<|,mid+,r,z);

     }

     pushup(rt);

 }

 void update2(int rt,int l,int r){

     if(t[rt].l>=l&&t[rt].r<=r){

         if(t[rt].mx==t[rt].mn){

            LL tem=(LL)sqrt(t[rt].mx);

            t[rt].sum=(LL)tem*t[rt].len;

            t[rt].lazy-=(t[rt].mx-tem);

            t[rt].mx=t[rt].mn=tem;

            return;

         }

         else if(t[rt].mx==t[rt].mn+){

             LL tem1=(LL)sqrt(t[rt].mx);

             LL tem2=(LL)sqrt(t[rt].mn);

             if(tem1==tem2+){

                 t[rt].sum-=(LL)(t[rt].mx-tem1)*t[rt].len;

                 t[rt].lazy-=(t[rt].mx-tem1);

                 t[rt].mx=tem1;

                 t[rt].mn=tem2;

                 return;

             }

         }

     }

     pushdown(rt);

     int mid=(t[rt].l+t[rt].r)>>;

     if(r<=mid) update2(rt<<,l,r);

     else if(l>mid) update2(rt<<|,l,r);

     else {

         update2(rt<<,l,mid);

         update2(rt<<|,mid+,r);

     }

     pushup(rt);

 }

 LL query(int rt,int l,int r){

     if(t[rt].l>=l&&t[rt].r<=r){

         return t[rt].sum;

     }

     pushdown(rt);

     int mid=(t[rt].l+t[rt].r)>>;

     if(r<=mid) return query(rt<<,l,r);

     else if(l>mid) return query(rt<<|,l,r);

     else {

         return query(rt<<,l,mid)+query(rt<<|,mid+,r);

     }

 }

 int main(){

     int T;

     scanf("%d",&T);

     while(T--){

        scanf("%d%d",&n,&q);

        for(int i=;i<=n;i++) {

         scanf("%d",&a[i]);

        }

        build(,,n);

        while(q--){

            int op,x,y,z;

            scanf("%d%d%d",&op,&x,&y);

            if(op==){

                scanf("%d",&z);

                update1(,x,y,z);

            }

            else if(op==){

                update2(,x,y);

            }

            else {

                LL ans=query(,x,y);

                printf("%I64d\n",ans);

            }

        }

     }

     return ;

 }