#![allow(non_snake_case)]



fn main(){
    use proconio::*;
    input!{
        n:usize,
        q:usize,
        a:[usize;n],
    }

    type T=(usize,usize); // val, len
    impl_monoid!(M,T,(0,0),|a:T,b:T|(a.0+b.0,a.1+b.1));
    impl_mapmonoid!(F,M,usize,!0,|v:T,f:usize|if f!=!0{(v.1*f,v.1)}else{v},|new:usize,old:usize|if new==!0{old}else{new});
    let mut seg=LazySegtree::<F>::from(a.iter().map(|&a|(a,1)).collect_vec());

    #[derive(Clone,Copy,PartialEq,Eq,PartialOrd,Ord)]
    struct Item{
        l:usize,
        r:usize,
        v:usize,
    }
    impl Item{
        fn new(l:usize)->Item{
            Item{l,r:0,v:0}
        }
    }
    
    let mut set=std::collections::BTreeSet::<Item>::new();
    for i in 0..n{
        if a[i]>1{
            set.insert(Item{l:i,r:i+1,v:a[i]});
        }
    }
    let mut rem=vec![];

    for _ in 0..q{
        input!{
            t:usize,
        }
        match t{
            0=>{
                input!{
                    l:usize,
                    r:usize,
                }
                // sum of l..r
                let ans=seg.prod(l..r).0;
                print!("{}\n",ans);
            },
            1=>{
                input!{
                    l:usize,
                    r:usize,
                    x:usize,
                }
                // assign x for l..r
                seg.apply(l..r,x);

                rem.clear();
                rem.extend(set.range(..Item::new(l)).last().copied());
                rem.extend(set.range(Item::new(l)..Item::new(r)).copied());
                for &item in &rem{
                    if item.r<=l || r<=item.l{
                        continue;
                    }

                    set.remove(&item);
                    if item.l<=l && l<item.r{
                        set.insert(Item{r:l,..item});
                    }
                    if item.l<=r && r<item.r{
                        set.insert(Item{l:r,..item});
                    }
                }

                if x>1{
                    set.insert(Item{l,r,v:x});
                }
            },
            2=>{
                input!{
                    l:usize,
                    r:usize,
                }
                // sqrt l..r

                rem.clear();
                rem.extend(set.range(..Item::new(l)).last().copied());
                rem.extend(set.range(Item::new(l)..Item::new(r)).copied());
                for &item in &rem{
                    if item.r<=l || r<=item.l{
                        continue;
                    }
                    
                    set.remove(&item);
                    if item.l<=l && l<item.r{
                        set.insert(Item{r:l,..item});
                    }
                    if item.l<=r && r<item.r{
                        set.insert(Item{l:r,..item});
                    }

                    let l=item.l.max(l);
                    let r=item.r.min(r);
                    let nv=item.v.isqrt();
                    
                    seg.apply(l..r,nv);
                    if nv>1{
                        set.insert(Item{l,r,v:nv});
                    }
                }
            },
            _=>panic!(),
        }
    }
}



use itertools::*;



// Compは(new,old)の順に引数を取る
#[derive(Clone)]
struct LazySegtree<F:MapMonoid>{
    n:usize,
    size:usize,
    log:usize,
    a:Vec<std::cell::Cell<<F::M as Monoid>::S>>,
    lazy:Vec<std::cell::Cell<F::F>>,
}
impl<F:MapMonoid> From<Vec<<F::M as Monoid>::S>> for LazySegtree<F>{
    fn from(v:Vec<<F::M as Monoid>::S>)->Self{
        let n=v.len();
        let size=n.next_power_of_two();
        let log=size.trailing_zeros() as usize;

        let mut a=vec![std::cell::Cell::new(F::M::e());2*size];
        let mut it=v.iter().map(|&a|std::cell::Cell::new(a));
        a[size..size+n].fill_with(||it.next().unwrap());
        for i in (1..size).rev(){
            a[i].set(F::M::op(a[i*2].get(),a[i*2+1].get()));
        }

        LazySegtree{
            n,size,log,
            a,lazy:vec![std::cell::Cell::new(F::id());size],
        }
    }
}
impl<F:MapMonoid> LazySegtree<F>{
    fn new(n:usize)->Self{
        let size=n.next_power_of_two();
        let log=size.trailing_zeros() as usize;
        Self{
            n,size,log,
            a:vec![std::cell::Cell::new(F::M::e());size*2],
            lazy:vec![std::cell::Cell::new(F::id());size],
        }
    }

    fn update(&self,k:usize){
        self.a[k].set(F::M::op(self.a[2*k].get(),self.a[2*k+1].get()));
    }
    
    fn apply_node(&self,k:usize,f:F::F){
        self.a[k].set(F::map(self.a[k].get(),f));
        if k<self.size{
            self.lazy[k].set(F::comp(f,self.lazy[k].get()));
        }
    }
    
    fn push(&self,k:usize){
        self.apply_node(2*k,self.lazy[k].get());
        self.apply_node(2*k+1,self.lazy[k].get());
        self.lazy[k].set(F::id());
    }
    
    fn set(&mut self,mut i:usize,v:<F::M as Monoid>::S){
        assert!(i<self.n);
        i+=self.size;
        for k in (1..=self.log).rev(){
            self.push(i>>k);
        }

        self.a[i].set(v);
        for k in 1..=self.log{
            self.update(i>>k);
        }
    }

    fn get(&self,mut i:usize)-><F::M as Monoid>::S{
        assert!(i<self.n);
        i+=self.size;
        for k in (1..=self.log).rev(){
            self.push(i>>k);
        }
        self.a[i].get()
    }

    fn prod(&self,range:impl std::ops::RangeBounds<usize>)-><F::M as Monoid>::S{
        use std::ops::Bound::*;
        let mut u=match range.start_bound(){
            Included(&a)=>a,
            Excluded(&a)=>a+1,
            Unbounded=>0,
        };
        let mut v=match range.end_bound(){
            Included(&a)=>a+1,
            Excluded(&a)=>a,
            Unbounded=>self.n,
        };
        assert!(u<=v && v<=self.n);

        if (u,v)==(0,self.n){
            return self.a[1].get();
        }
        if u==v{
            return F::M::e();
        }

        u+=self.size;
        v+=self.size;

        for i in (1..=self.log).rev(){
            if u&!0<<i!=u{
                self.push(u>>i);
            }
            if v&!0<<i!=v{
                self.push(v>>i);
            }
        }

        let mut um=F::M::e();
        let mut vm=F::M::e();
        while u<v{
            if u&1!=0{
                um=F::M::op(um,self.a[u].get());
                u+=1;
            }
            if v&1!=0{
                v-=1;
                vm=F::M::op(self.a[v].get(),vm);
            }
            u>>=1;
            v>>=1;
        }

        F::M::op(um,vm)
    }

    fn apply(&mut self,range:impl std::ops::RangeBounds<usize>,f:F::F){
        use std::ops::Bound::*;
        let mut u=match range.start_bound(){
            Included(&a)=>a,
            Excluded(&a)=>a+1,
            Unbounded=>0,
        };
        let mut v=match range.end_bound(){
            Included(&a)=>a+1,
            Excluded(&a)=>a,
            Unbounded=>self.n,
        };
        assert!(u<=v && v<=self.n);

        if u==v{
            return;
        }

        u+=self.size;
        v+=self.size;

        for i in (1..=self.log).rev(){
            if u&!0<<i!=u{
                self.push(u>>i);
            }
            if v&!0<<i!=v{
                self.push(v-1>>i);
            }
        }

        {
            let mut u=u;
            let mut v=v;
            while u<v{
                if u&1!=0{
                    self.apply_node(u,f);
                    u+=1;
                }
                if v&1!=0{
                    v-=1;
                    self.apply_node(v,f);
                }
                u>>=1;
                v>>=1;
            }
        }

        for i in 1..=self.log{
            if u&!0<<i!=u{
                self.update(u>>i);
            }
            if v&!0<<i!=v{
                self.update(v-1>>i);
            }
        }
    }

    // l..rがtrueで、l..=rがfalse
    fn max_right(&self,mut l:usize,mut f:impl FnMut(<F::M as Monoid>::S)->bool)->usize{
        assert!(l<=self.n && f(F::M::e()));
        if l==self.n{
            return self.n;
        }

        l+=self.size;
        for i in (1..=self.log).rev(){
            self.push(l>>i);
        }

        let mut m=F::M::e();
        loop{
            l>>=l.trailing_zeros();

            if !f(F::M::op(m,self.a[l].get())){
                while l<self.size{
                    self.push(l);
                    l*=2;
                    let res=F::M::op(m,self.a[l].get());
                    if f(res){
                        m=res;
                        l+=1;
                    }
                }
                return l-self.size;
            }

            m=F::M::op(m,self.a[l].get());
            l+=1;
            if l&l.wrapping_neg()==l{
                return self.n;
            }
        }
    }

    // l..rがtrueで、l-1..rがfalse
    fn min_left(&mut self,mut r:usize,mut f:impl FnMut(<F::M as Monoid>::S)->bool)->usize{
        assert!(r<=self.n && f(F::M::e()));
        if r==0{
            return 0;
        }

        r+=self.size;
        for i in (1..=self.log).rev(){
            self.push(r-1>>i);
        }

        let mut m=F::M::e();
        loop{
            r-=1;
            r>>=r.trailing_ones();
            r=r.max(1);
            
            if !f(F::M::op(self.a[r].get(),m)){
                while r<self.size{
                    self.push(r);
                    r=2*r+1;
                    let res=F::M::op(self.a[r].get(),m);
                    if f(res){
                        m=res;
                        r-=1;
                    }
                }

                return r+1-self.size;
            }

            m=F::M::op(self.a[r].get(),m);
            if r&r.wrapping_neg()==r{
                return 0;
            }
        }
    }
}


trait Monoid{
    type S:Copy;
    fn e()->Self::S;
    fn op(left:Self::S,right:Self::S)->Self::S;
}


#[macro_export]
macro_rules! impl_monoid{
    ($t:ident,$item:ty,$e:expr,$op:expr)=>{
        #[derive(Clone,Copy)]
        struct $t();
        impl Monoid for $t{
            type S=$item;
            fn e()->$item{ $e }
            fn op(left:$item,right:$item)->$item{
                $op(left,right)
            }
        }
    };
}


trait MapMonoid{
    type M:Monoid;
    type F:Copy;
    fn id()->Self::F;
    fn map(v:<Self::M as Monoid>::S,f:Self::F)-><Self::M as Monoid>::S;
    fn comp(new:Self::F,old:Self::F)->Self::F;
}


#[macro_export]
macro_rules! impl_mapmonoid{
    ($t:ident,$monoid:ty,$f:ty,$id:expr,$map:expr,$comp:expr)=>{
        #[derive(Clone,Copy)]
        struct $t();
        impl MapMonoid for $t{
            type M=$monoid;
            type F=$f;
            fn id()->$f{ $id }
            fn map(v:<$monoid as Monoid>::S,f:$f)-><$monoid as Monoid>::S{
                $map(v,f)
            }
            fn comp(new:$f,old:$f)->$f{
                $comp(new,old)
            }
        }
    }
}