#include<bits/stdc++.h>
#define re register
using namespace std;
int n,m,a[500010],cmd,t1,t2,t3;
long long ans;
inline int read(){
	int f=1,x=0;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
inline void write(long long t){
	if(t>9) write(t/10);
	putchar(t%10+'0');
}
signed main(){
	re int i,j;
	n=read(),m=read();
	for(i=1;i<=n;i++) a[i]=read();
	for(i=1;i<=m;i++){
		cmd=read();
		if(cmd==1){
			t1=read(),t2=read(),t3=read();
			if(t3==1) continue;
			if(t3==2){
				for(j=t1;j<=t2-5;j+=6){
					(a[j]&1)?1:(a[j]>>=1);
					(a[j+1]&1)?1:(a[j+1]>>=1);
					(a[j+2]&1)?1:(a[j+2]>>=1);
					(a[j+3]&1)?1:(a[j+3]>>=1);
					(a[j+4]&1)?1:(a[j+4]>>=1);
					(a[j+5]&1)?1:(a[j+5]>>=1);
				}
				while(t2-j+1){
					(a[j]&1)?1:(a[j]>>=1);
					j++;
				}
			}else if(t3==4){
				for(j=t1;j<=t2-5;j+=6){
					(a[j]&3)?1:(a[j]>>=2);
					(a[j+1]&3)?1:(a[j+1]>>=2);
					(a[j+2]&3)?1:(a[j+2]>>=2);
					(a[j+3]&3)?1:(a[j+3]>>=2);
					(a[j+4]&3)?1:(a[j+4]>>=2);
					(a[j+5]&3)?1:(a[j+5]>>=2);
				}
				while(t2-j+1){
					(a[j]&3)?1:(a[j]>>=2);
					j++;
				}
			}else if(t3==8){
				for(j=t1;j<=t2-5;j+=6){
					(a[j]&7)?1:(a[j]>>=3);
					(a[j+1]&7)?1:(a[j+1]>>=3);
					(a[j+2]&7)?1:(a[j+2]>>=3);
					(a[j+3]&7)?1:(a[j+3]>>=3);
					(a[j+4]&7)?1:(a[j+4]>>=3);
					(a[j+5]&7)?1:(a[j+5]>>=3);
				}
				while(t2-j+1){
					(a[j]&7)?1:(a[j]>>=3);
					j++;
				}
			}else{
				for(j=t1;j<=t2-5;j+=6){
					(a[j]%t3)?1:(a[j]/=t3);
					(a[j+1]%t3)?1:(a[j+1]/=t3);
					(a[j+2]%t3)?1:(a[j+2]/=t3);
					(a[j+3]%t3)?1:(a[j+3]/=t3);
					(a[j+4]%t3)?1:(a[j+4]/=t3);
					(a[j+5]%t3)?1:(a[j+5]/=t3);
				}
				while(t2-j+1){
					(a[j]%t3)?1:(a[j]/=t3);
					j++;
				}
			}
		}else{
			t1=read(),t2=read();
			ans=0;
			for(j=t1;j<=t2-5;j+=6) ans+=(a[j]+a[j+1]+a[j+2]+a[j+3]+a[j+4]+a[j+5]);
			while(t2-j+1){
				ans+=a[j];
				j++;
			}
			write(ans);
			putchar('\n');
		}
	}
}