RT

#include<bits/stdc++.h>
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;
typedef long long ll;
const ll MAXN=5e5+5,MAXL=1e5+5;
ll n,m;
int a[MAXL];
namespace DSU{
    basic_string<int> S[MAXN],dsu[MAXN];
    inline int find(int num,int now){
        return (now==(int)(dsu[num].size())||now==dsu[num][now])?now:dsu[num][now]=find(num,dsu[num][now]);
    }
}
using DSU::S;
using DSU::dsu;
ll bit[MAXL];
#define lowbit(x) (x&-x)
inline void add(int pos,int num){
	while(pos<=n){
		bit[pos]+=num;
		pos+=lowbit(pos);
	}
	return;
}
inline ll sum(int pos){
	ll ans=0;
	while(pos){
		ans+=bit[pos];
		pos-=lowbit(pos);
	}
	return ans;
}
int op,l,r,x;
inline void update(int L,int R,int X){
	int pos=lower_bound(S[X].begin(),S[X].end(),L)-S[X].begin();
	for(int i=DSU::find(X,pos);i<(int)(S[X].size())&&S[X][i]<=R;i=DSU::find(X,i+1)){
		if(!(a[S[X][i]]%X)){
			add(S[X][i],a[S[X][i]]/X-a[S[X][i]]);
			a[S[X][i]]/=X;
		}
		if(a[S[X][i]]%X)dsu[X][i]=i+1;
	}
    return;
}
inline ll query(int L,int R){
	return sum(R)-sum(L-1);
}
const int Size=(1<<20)+1;
char buf[Size],*p1=buf,*p2=buf;
char buffer[Size];
int op1=-1;
const int op2=Size-1;
inline char readchar() {
	if(p1!=p2) {
		return *p1++;
	}
	return p1==(p2=(p1=buf)+fread(buf,1,Size-1,stdin))?EOF:*p1++;
}
inline void flush() {
	fwrite(buffer,1,op1+1,stdout),op1=-1;
}
inline void writechar(const char &x) {
	if(op1==op2) flush();
	buffer[++op1]=x;
}
#ifndef ONLINE_JUDGE
#define readchar getchar
#endif
#define putchar writechar
inline int read() {
	int s=1,c=readchar(),x=0;
	while(c<=32) {
		c=readchar();
	}
	if(c=='-') {
		s=-1,c=readchar();
	}
	for(; ('0'<=c && c<='9'); c=readchar()) {
		x=x*10+c-'0';
	}
	return x*s;
}
inline void write(long long x) {
	if(x<0) {
		writechar('-'),x=-x;
	}
	char s[25];
	int n=0;
	while(x || !n) {
		s[n++]='0'+x%10,x/=10;
	}
	while(n--) {
		writechar(s[n]);
	}
}
ll lstans;
int qwq;
int qaq[305]={0,2,3,4,5,6,7,8,9,10,11,12,14,15,16,18,20,21,22,24,27,28,30,33,35,36,40,42,44,45,48,54,55,56,60,63,66,70,72,77,80,81,84,88,90,99,105,108,110,112,120,126,132,135,140,144,154,162,165,168,176,180,189,198,210,216,220,231,240,252,264,270,280,297,308,315,324,330,336,360,378,385,396,405,420,432,440,462,495,504,528,540,560,567,594,616,630,648,660,693,720,756,770,792,810,840,880,891,924,945,990,1008,1080,1134,1155,1188,1232,1260,1296,1320,1386,1485,1512,1540,1584,1620,1680,1782,1848,1890,1980,2079,2160,2268,2310,2376,2520,2640,2772,2835,2970,3024,3080,3240,3465,3564,3696,3780,3960,4158,4455,4536,4620,4752,5040,5544,5670,5940,6160,6237,6480,6930,7128,7560,7920,8316,8910,9072,9240,10395,11088,11340,11880,12474,13860,14256,15120,16632,17820,18480,20790,22680,23760,24948,27720,31185,33264,35640,41580,45360,49896,55440,62370,71280,83160,99792,124740,166320,249480,498960};
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		qwq=max(a[i],qwq);
		if(a[i]==498960){
			for(int j=1;j<=200;j++){
				if(!j)continue;
				S[qaq[j]].push_back(i);
				dsu[qaq[j]].push_back(dsu[qaq[j]].size());
			}
			add(i,a[i]);
			continue;
		}
		ll lim=sqrt(a[i]);
		for(int j=1;j<=lim;j++){
			if(!(a[i]%j)){
                if(j>1){
				    S[j].push_back(i);
				    dsu[j].push_back(dsu[j].size());
                }
				if(j*j<a[i]&&a[i]/j>1){
					S[a[i]/j].push_back(i);
					dsu[a[i]/j].push_back(dsu[a[i]/j].size());
				}
			}
		}
		add(i,a[i]);
	}
	for(int i=1;i<=m;i++){
		op=read();
		if(op==1){
			l=read(),r=read(),x=read();
			l^=lstans,r^=lstans,x^=lstans; 
			if(x>1&&x<=qwq)update(l,r,x);
		}
		else{
			l=read(),r=read();
			l^=lstans,r^=lstans; 
			write(lstans=query(l,r));
			putchar('\n');
		}
	}
	flush();
	return 0;
}