#include<bits/stdc++.h>

 using namespace std;

 const int N=1e5+;

 long long a[N];

 struct node{

     int l,r;

     long long maxx,minn,sum;

     long long lazy;

     void up(long long val){

         maxx+=val;minn+=val;sum+=(r-l+)*1ll*val;

         lazy+=val;

     }

 }tree[*N];

 void push_up(int x){

     tree[x].maxx=max(tree[x<<].maxx,tree[x<<|].maxx);

     tree[x].minn=min(tree[x<<].minn,tree[x<<|].minn);

     tree[x].sum=tree[x<<].sum+tree[x<<|].sum;

 }

 void push_down(int x){

     long long val=tree[x].lazy;

     if(val){

         tree[x<<].up(val);

         tree[x<<|].up(val);

         tree[x].lazy=;

     }

 }

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

     tree[x].l=l;  tree[x].r=r;

     tree[x].lazy=tree[x].sum=;

     if(l==r){

         tree[x].minn=tree[x].maxx=tree[x].sum=a[l];

         return;

     }

     int m=(l+r)/;

     build(x<<,l,m);

     build(x<<|,m+,r);

     push_up(x);

 }

 void updata(int x,int l,int r,long long val){

     int L=tree[x].l,R=tree[x].r;

     if(l<=L&&R<=r){

         tree[x].up(val);return;

     }

     int m=(L+R)/;

     push_down(x);

     if(l<=m) updata(x<<,l,r,val);

     if(r>m) updata(x<<|,l,r,val);

     push_up(x);

 }

 void Sqrt(int x,int l,int r){

     push_down(x);

     int L=tree[x].l,R=tree[x].r;

     if(l<=L&&R<=r){

         if(tree[x].maxx==tree[x].minn){

             long long t=(long long)sqrt(tree[x].maxx);

             updata(x,L,R,t-tree[x].maxx);

             return;

         }

         else if(tree[x].minn+==tree[x].maxx){

             long long t1=(long long)sqrt(tree[x].minn);

             long long t2=(long long)sqrt(tree[x].maxx);

             if(t1+==t2){

                 updata(x,L,R,t2-tree[x].maxx);

                 return;

             }

         }

     }

     int m=(L+R)/;

     if(l<=m) Sqrt(x<<,l,r);

     if(r>m) Sqrt(x<<|,l,r);

     push_up(x);

 }

 long long query(int x,int l,int r){

     push_down(x);

     int L=tree[x].l,R=tree[x].r;

     if(l<=L&&R<=r){

         return tree[x].sum;

     }

     int m=(L+R)/;

     long long ans=;

     if(l<=m) ans+=query(x<<,l,r);

     if(r>m) ans+=query(x<<|,l,r);

     push_up(x);

     return ans;

 }

 int main(){

     int n,m;

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

     for(int i=;i<=n;i++) scanf("%lld",&a[i]);

     build(,,n);

     while(m--){

         int op,l,r;

         scanf("%d%d%d",&op,&l,&r);

         if(op==){

             long long val;

             scanf("%lld",&val);

             updata(,l,r,val);

         }

         else if(op==){

             Sqrt(,l,r);

         }

         else{

             printf("%lld\n",query(,l,r));

         }

     }

     return ;

 }