import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N,Q=list(map(int,input().split()))
A=list(map(int,input().split()))

sq=int(N**(1/2))
LEN=(N+sq-1)//sq
lastLEN=N%sq
UNIT=[-1]*LEN
SUM=[0]*LEN
for i in range(LEN):
    one=-1
    for j in range(i*sq,min(N,i*sq+sq)):
        if one==-1:
            one=A[j]
        elif one==A[j]:
            pass
        else:
            one=-2
        SUM[i]+=A[j]

    #print(LIST)
        
    if one>=0:
        UNIT[i]=one

LANS=[]
for tests in range(Q):
    #print(A)
    L=list(map(int,input().split()))

    if L[0]==0:
        l,r=L[1],L[2]
        ANS=0

        now=l
        while now<r and now%sq!=0:
            if UNIT[now//sq]!=-1:
                ANS+=UNIT[now//sq]
            else:
                ANS+=A[now]
            now+=1

        while now<r and now+sq<r:
            ANS+=SUM[now//sq]
            now+=sq

        while now<r:
            if UNIT[now//sq]!=-1:
                ANS+=UNIT[now//sq]
            else:
                ANS+=A[now]
            now+=1

        LANS.append(ANS)

    elif L[0]==1:
        l,r,x=L[1:]

        now=l
        while now<r and now%sq!=0:
            if UNIT[now//sq]!=-1:
                ume=UNIT[now//sq]
                UNIT[now//sq]=-1
                SUM[now//sq]=0

                for i in range(now//sq*sq,min(N,now//sq*sq+sq)):
                    A[i]=ume
                    SUM[now//sq]+=A[i]

            SUM[now//sq]-=A[now]
            A[now]=x
            SUM[now//sq]+=A[now]
            now+=1

        while now<r and now+sq<r:
            UNIT[now//sq]=x
            SUM[now//sq]=x*sq
            now+=sq

        while now<r:
            if UNIT[now//sq]!=-1:
                ume=UNIT[now//sq]
                UNIT[now//sq]=-1
                SUM[now//sq]=0

                for i in range(now//sq*sq,min(N,now//sq*sq+sq)):
                    A[i]=ume
                    SUM[now//sq]+=A[i]

            SUM[now//sq]-=A[now]
            A[now]=x
            SUM[now//sq]+=A[now]
            now+=1

    elif L[0]==2:
        l,r=L[1],L[2]

        now=l
        while now<r and now%sq!=0:
            if UNIT[now//sq]!=-1:
                ume=UNIT[now//sq]
                UNIT[now//sq]=-1
                SUM[now//sq]=0

                for i in range(now//sq*sq,min(N,now//sq*sq+sq)):
                    A[i]=ume
                    SUM[now//sq]+=A[i]

            SUM[now//sq]-=A[now]
            A[now]=int(A[now]**(1/2))
            SUM[now//sq]+=A[now]
            now+=1

        while now<r and now+sq<r:
            if UNIT[now//sq]!=-1:
                ume=int(UNIT[now//sq]**(1/2))
                UNIT[now//sq]=ume
                SUM[now//sq]=ume*sq
                now+=sq
            else:
                one=-1
                SUM[now//sq]=0
                for i in range(now,now+sq):
                    A[i]=int(A[i]**(1/2))
                    SUM[now//sq]+=A[i]
                    if one==-1:
                        one=A[i]
                    elif one==A[i]:
                        pass
                    else:
                        one=-2

                if one>=0:
                    UNIT[now//sq]=one
                    SUM[now//sq]=one*sq
                now+=sq
        while now<r:
            if UNIT[now//sq]!=-1:
                ume=UNIT[now//sq]
                UNIT[now//sq]=-1
                SUM[now//sq]=0

                for i in range(now//sq*sq,min(N,now//sq*sq+sq)):
                    A[i]=ume
                    SUM[now//sq]+=A[i]

            SUM[now//sq]-=A[now]
            A[now]=int(A[now]**(1/2))
            SUM[now//sq]+=A[now]
            now+=1

        
        
print("\n".join(map(str,LANS)))