import sys
input = sys.stdin.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):
    LIST=[]
    for j in range(i*sq,min(N,i*sq+sq)):
        LIST.append(A[j])
        SUM[i]+=A[j]

    #print(LIST)
        
    if len(set(LIST))==1:
        UNIT[i]=LIST[0]

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

        print(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*r
            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:
                LIST=[]
                SUM[now//sq]=0
                for i in range(now,now+sq):
                    A[i]=int(A[i]**(1/2))
                    SUM[now//sq]+=A[i]
                    LIST.append(A[i])

                if len(set(LIST))==1:
                    UNIT[i]=LIST[0]
                    SUM[now//sq]=LIST[0]*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