//It's all about what U BELIEVE
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<bitset>
#include<vector>
#include<cstring>
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define endl '\n'
#define PI acos(-1)
#define INF ~(1<<31)
#define pb push_back
#define pob pop_back
#define wtm while(t--)
#define wnm while(n--)
#define MOD 1000000007
#define lsone(Z) (Z&-Z)
#define gcu getchar_unlocked
#define allof(Z) Z.begin(),Z.end()
#define rallof(Z) Z.rbegin(),Z.rend()
#define mset(z,v) memset(z,v,sizeof(z))
#define lne if(line)puts("");else line =1
#define fo(s,y,z) for(int y=s ; y<(int)z ; y++)
#define readf freopen("/home/ebram96/Desktop/in" , "r" , stdin);
#define writef freopen("/home/ebram96/Desktop/out" , "w" , stdout);
using namespace std;
typedef unsigned long long ull;
typedef pair<ull,ull> pairull;
typedef pair<int,int> pairii;
typedef vector<string> vstr;
typedef deque<int> dqint;
typedef set<ull> setull;
typedef unsigned int ui;
typedef queue<int> qint;
typedef vector<int> vi;
typedef set<int> seti;
typedef long long ll;
//int dx[]={-1,0,1, 0,-1,1, 1,-1};
//int dy[]={ 0,1,0,-1, 1,1,-1,-1};
const int N = 300001;
ll sum[N<<2];
pairii mx[N<<2]; // first = value , second = index in array
int n , m , a[N] , d[1000001] , t , l , r;
void calculateDivisors()
{
for(int i = 1 ; i < 1000001 ; i++)
for(int j = i ; j < 1000001 ; j+=i)
d[j]++;
}
void updateMax(int &i,int v,int node,int tl,int tr)
{
if(tl==tr)
{
mx[node] = {v,i};
return;
}
int mid = (tl+tr)>>1;
if(i<=mid)
updateMax(i,v,node<<1,tl,mid);
else
updateMax(i,v,(node<<1)+1,mid+1,tr);
pairii a = mx[node<<1],
b = mx[(node<<1)+1];
mx[node] = (a.first>b.first?a:b);
}
pairii getMax(int node,int &l,int &r,int tl,int tr)
{
if(l>tr||r<tl)
return {-1,-1};
if(tl>=l&&tr<=r)
return mx[node];
int mid = (tl+tr)>>1;
pairii a = getMax(node<<1,l,r,tl,mid),
b = getMax((node<<1)+1,l,r,mid+1,tr);
return mx[node] = (a.first>b.first?a:b);
}
void updateSum(int &i,int node,int tl,int tr)
{
if(tl==tr)
{
sum[node] = a[i];
return ;
}
int mid = (tl+tr)>>1;
if(i<=mid)
updateSum(i,node<<1,tl,mid);
else
updateSum(i,(node<<1)+1,mid+1,tr);
sum[node] = sum[node<<1] + sum[(node<<1)+1];
}
ll getSum(int &l,int &r,int node,int tl,int tr)
{
if(l>tr||r<tl)
return 0;
if(tl>=l&&tr<=r)
return sum[node];
int mid = (tl+tr)>>1;
return
getSum(l,r,node<<1,tl,mid)+
getSum(l,r,(node<<1)+1,mid+1,tr);
}
int main()
{
//readf
calculateDivisors();
scanf("%d %d",&n,&m);
fo(1,y,n+1)
{
scanf("%d",&a[y]);
updateMax(y,a[y],1,1,n);
updateSum(y,1,1,n);
}
while(m--)
{
scanf("%d %d %d",&t,&l,&r);
if(t==1)
{
pairii ret = getMax(1,l,r,1,n);
vi tmp;
while(ret.first > 2)//skip all indices with a[i] <= 2
{
////set to a low value to avoid applying
////the query on the same index in the array:
updateMax(ret.second,-1,1,1,n);
tmp.pb(ret.second);
ret = getMax(1,l,r,1,n);
}
int sz = tmp.size();
fo(0,y,sz)
{
//update the array
a[tmp[y]] = d[a[tmp[y]]];
updateSum(tmp[y],1,1,n);
updateMax(tmp[y],a[tmp[y]],1,1,n);
}
}
else
printf("%lld\n",getSum(l,r,1,1,n));
}
}
Ly9JdCdzIGFsbCBhYm91dCB3aGF0IFUgQkVMSUVWRQojaW5jbHVkZTxtYXA+CiNpbmNsdWRlPHNldD4KI2luY2x1ZGU8c3RhY2s+CiNpbmNsdWRlPHF1ZXVlPgojaW5jbHVkZTxkZXF1ZT4KI2luY2x1ZGU8Y21hdGg+CiNpbmNsdWRlPGJpdHNldD4KI2luY2x1ZGU8dmVjdG9yPgojaW5jbHVkZTxjc3RyaW5nPgojaW5jbHVkZTxzdGRpby5oPgojaW5jbHVkZTxpb3N0cmVhbT4KI2luY2x1ZGU8YWxnb3JpdGhtPgojZGVmaW5lIGVuZGwgJ1xuJwojZGVmaW5lIFBJIGFjb3MoLTEpCiNkZWZpbmUgSU5GIH4oMTw8MzEpCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgcG9iIHBvcF9iYWNrCiNkZWZpbmUgd3RtIHdoaWxlKHQtLSkKI2RlZmluZSB3bm0gd2hpbGUobi0tKQojZGVmaW5lIE1PRCAxMDAwMDAwMDA3CiNkZWZpbmUgbHNvbmUoWikgKFomLVopCiNkZWZpbmUgZ2N1IGdldGNoYXJfdW5sb2NrZWQKI2RlZmluZSBhbGxvZihaKSBaLmJlZ2luKCksWi5lbmQoKQojZGVmaW5lIHJhbGxvZihaKSBaLnJiZWdpbigpLFoucmVuZCgpCiNkZWZpbmUgbXNldCh6LHYpIG1lbXNldCh6LHYsc2l6ZW9mKHopKQojZGVmaW5lIGxuZSBpZihsaW5lKXB1dHMoIiIpO2Vsc2UgbGluZSA9MQojZGVmaW5lIGZvKHMseSx6KSBmb3IoaW50IHk9cyA7IHk8KGludCl6IDsgeSsrKQojZGVmaW5lIHJlYWRmIGZyZW9wZW4oIi9ob21lL2VicmFtOTYvRGVza3RvcC9pbiIgLCAiciIgLCBzdGRpbik7CiNkZWZpbmUgd3JpdGVmIGZyZW9wZW4oIi9ob21lL2VicmFtOTYvRGVza3RvcC9vdXQiICwgInciICwgc3Rkb3V0KTsKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgdWxsOwp0eXBlZGVmIHBhaXI8dWxsLHVsbD4gcGFpcnVsbDsKdHlwZWRlZiBwYWlyPGludCxpbnQ+IHBhaXJpaTsKdHlwZWRlZiB2ZWN0b3I8c3RyaW5nPiB2c3RyOwp0eXBlZGVmIGRlcXVlPGludD4gZHFpbnQ7CnR5cGVkZWYgc2V0PHVsbD4gc2V0dWxsOwp0eXBlZGVmIHVuc2lnbmVkIGludCB1aTsKdHlwZWRlZiBxdWV1ZTxpbnQ+IHFpbnQ7CnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CnR5cGVkZWYgc2V0PGludD4gc2V0aTsKdHlwZWRlZiBsb25nIGxvbmcgbGw7Ci8vaW50IGR4W109ey0xLDAsMSwgMCwtMSwxLCAxLC0xfTsKLy9pbnQgZHlbXT17IDAsMSwwLC0xLCAxLDEsLTEsLTF9Owpjb25zdCBpbnQgTiA9IDMwMDAwMTsKbGwgc3VtW048PDJdOwpwYWlyaWkgbXhbTjw8Ml07IC8vIGZpcnN0ID0gdmFsdWUgLCBzZWNvbmQgPSBpbmRleCBpbiBhcnJheQppbnQgbiAsIG0gLCBhW05dICwgZFsxMDAwMDAxXSAsIHQgLCBsICwgcjsKdm9pZCBjYWxjdWxhdGVEaXZpc29ycygpCnsKCWZvcihpbnQgaSA9IDEgOyBpIDwgMTAwMDAwMSA7IGkrKykKCQlmb3IoaW50IGogPSBpIDsgaiA8IDEwMDAwMDEgOyBqKz1pKQoJCQlkW2pdKys7Cn0Kdm9pZCB1cGRhdGVNYXgoaW50ICZpLGludCB2LGludCBub2RlLGludCB0bCxpbnQgdHIpCnsKCWlmKHRsPT10cikKCXsKCQlteFtub2RlXSA9IHt2LGl9OwoJCXJldHVybjsKCX0KCWludCBtaWQgPSAodGwrdHIpPj4xOwoJaWYoaTw9bWlkKQoJCXVwZGF0ZU1heChpLHYsbm9kZTw8MSx0bCxtaWQpOwoJZWxzZQoJCXVwZGF0ZU1heChpLHYsKG5vZGU8PDEpKzEsbWlkKzEsdHIpOwoJcGFpcmlpIGEgPSBteFtub2RlPDwxXSwKCQkJYiA9IG14Wyhub2RlPDwxKSsxXTsKCW14W25vZGVdID0gKGEuZmlyc3Q+Yi5maXJzdD9hOmIpOwp9CnBhaXJpaSBnZXRNYXgoaW50IG5vZGUsaW50ICZsLGludCAmcixpbnQgdGwsaW50IHRyKQp7CglpZihsPnRyfHxyPHRsKQoJCXJldHVybiB7LTEsLTF9OwoJaWYodGw+PWwmJnRyPD1yKQoJCXJldHVybiBteFtub2RlXTsKCWludCBtaWQgPSAodGwrdHIpPj4xOwoJcGFpcmlpIGEgPSBnZXRNYXgobm9kZTw8MSxsLHIsdGwsbWlkKSwKCQkJYiA9IGdldE1heCgobm9kZTw8MSkrMSxsLHIsbWlkKzEsdHIpOwoJcmV0dXJuIG14W25vZGVdID0gKGEuZmlyc3Q+Yi5maXJzdD9hOmIpOwp9CnZvaWQgdXBkYXRlU3VtKGludCAmaSxpbnQgbm9kZSxpbnQgdGwsaW50IHRyKQp7CglpZih0bD09dHIpCgl7CgkJc3VtW25vZGVdID0gYVtpXTsKCQlyZXR1cm4gOwoJfQoJaW50IG1pZCA9ICh0bCt0cik+PjE7CglpZihpPD1taWQpCgkJdXBkYXRlU3VtKGksbm9kZTw8MSx0bCxtaWQpOwoJZWxzZQoJCXVwZGF0ZVN1bShpLChub2RlPDwxKSsxLG1pZCsxLHRyKTsKCXN1bVtub2RlXSA9IHN1bVtub2RlPDwxXSArIHN1bVsobm9kZTw8MSkrMV07Cn0KbGwgZ2V0U3VtKGludCAmbCxpbnQgJnIsaW50IG5vZGUsaW50IHRsLGludCB0cikKewoJaWYobD50cnx8cjx0bCkKCQlyZXR1cm4gMDsKCWlmKHRsPj1sJiZ0cjw9cikKCQlyZXR1cm4gc3VtW25vZGVdOwoJaW50IG1pZCA9ICh0bCt0cik+PjE7CglyZXR1cm4KCQkJZ2V0U3VtKGwscixub2RlPDwxLHRsLG1pZCkrCgkJCWdldFN1bShsLHIsKG5vZGU8PDEpKzEsbWlkKzEsdHIpOwp9CmludCBtYWluKCkKewoJLy9yZWFkZgoJY2FsY3VsYXRlRGl2aXNvcnMoKTsKCXNjYW5mKCIlZCAlZCIsJm4sJm0pOwoJZm8oMSx5LG4rMSkKCXsKCQlzY2FuZigiJWQiLCZhW3ldKTsKCQl1cGRhdGVNYXgoeSxhW3ldLDEsMSxuKTsKCQl1cGRhdGVTdW0oeSwxLDEsbik7Cgl9Cgl3aGlsZShtLS0pCgl7CgkJc2NhbmYoIiVkICVkICVkIiwmdCwmbCwmcik7CgkJaWYodD09MSkKCQl7CgkJCXBhaXJpaSByZXQgPSBnZXRNYXgoMSxsLHIsMSxuKTsKCQkJdmkgdG1wOwoJCQl3aGlsZShyZXQuZmlyc3QgPiAyKS8vc2tpcCBhbGwgaW5kaWNlcyB3aXRoIGFbaV0gPD0gMgoJCQl7CgkJCQkvLy8vc2V0IHRvIGEgbG93IHZhbHVlIHRvIGF2b2lkIGFwcGx5aW5nCgkJCQkvLy8vdGhlIHF1ZXJ5IG9uIHRoZSBzYW1lIGluZGV4IGluIHRoZSBhcnJheToKCQkJCXVwZGF0ZU1heChyZXQuc2Vjb25kLC0xLDEsMSxuKTsKCQkJCXRtcC5wYihyZXQuc2Vjb25kKTsKCQkJCXJldCA9IGdldE1heCgxLGwsciwxLG4pOwoJCQl9CgkJCWludCBzeiA9IHRtcC5zaXplKCk7CgkJCWZvKDAseSxzeikKCQkJewoJCQkJLy91cGRhdGUgdGhlIGFycmF5CgkJCQlhW3RtcFt5XV0gPSBkW2FbdG1wW3ldXV07CgkJCQl1cGRhdGVTdW0odG1wW3ldLDEsMSxuKTsKCQkJCXVwZGF0ZU1heCh0bXBbeV0sYVt0bXBbeV1dLDEsMSxuKTsKCQkJfQoJCX0KCQllbHNlCgkJCXByaW50ZigiJWxsZFxuIixnZXRTdW0obCxyLDEsMSxuKSk7Cgl9Cn0K