#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int M = 1e5 + 1;
ll seg[M*2][2], lz[M*2][2];
map<int,set<pair<int,int>>> rng;
void push(int v,int s,int e,int i)
{
int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2;
seg[lc][i]=(mid-s)*lz[v][i], lz[lc][i]=lz[v][i];
seg[rc][i]=(e-mid)*lz[v][i], lz[rc][i]=lz[v][i];
lz[v][i]=-1;
}
void modify(int l,int r,int x,int i,int v=0,int s=0,int e=M)
{
if (l>=e or r<=s) return;
if (l<=s && e<=r)
{
lz[v][i]=x;
seg[v][i]=(e-s)*lz[v][i];
return;
}
int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2;
if (~lz[v][i]) push(v,s,e,i);
modify(l,r,x,i,lc,s,mid);
modify(l,r,x,i,rc,mid,e);
seg[v][i]=seg[lc][i]+seg[rc][i];
}
ll get(int l,int r,int i,int v=0,int s=0,int e=M)
{
if (l>=e or r<=s) return 0;
if (l<=s && e<=r) return seg[v][i];
int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2;
if (~lz[v][i]) push(v,s,e,i);
return get(l,r,i,lc,s,mid)+get(l,r,i,rc,mid,e);
}
void add(int x,int i)
{
auto it=rng[x].upper_bound({i,0});
pair<int,int> pv={-1,-1}, nx={-1,-1};
if (it!=rng[x].end())
nx=*it;
if (it!=rng[x].begin())
it--, pv=*it;
if (~pv.first && ~nx.first && pv.second+2==nx.first)
{
rng[x].erase(pv), rng[x].erase(nx);
rng[x].insert({pv.first,nx.second});
}
else if(~pv.first && pv.second==i-1)
rng[x].erase(pv), pv.second++, rng[x].insert(pv);
else if(~nx.first && nx.first==i+1)
rng[x].erase(nx), nx.first--, rng[x].insert(nx);
else
rng[x].insert({i,i});
}
void rem(int x,int i)
{
auto it=rng[x].upper_bound({i+1,0});
it--;
pair<int,int> p=*it;
rng[x].erase(it);
if (p.first!=i) rng[x].insert({p.first,i-1});
if (p.second!=i) rng[x].insert({i+1,p.second});
}
ll val(ll l,ll r,int i)
{
int x=get(l,r,i)-r*(r-1)/2+l*(l-1)/2;
if (!i) x*=-1;
return x+r-l;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(NULL), cout.tie(NULL);
for (int i=0;i<M*2;i++) lz[i][0]=lz[i][1]=-1;
int n,q;
cin>>n>>q;
set<int> se;
int a[n];
for (int i=0;i<n;i++)
cin>>a[i], se.insert(a[i]);
vector<array<int,3>> v;
while (q--)
{
int t, l, r;
cin>>t>>l>>r;
l--;
v.push_back({t,l,r});
if (t==1) se.insert(r);
}
map<int,vector<int>> pr;
for (int i:se)
{
int x=i;
for (int p=2;p*p<=x;p+=1+p%2)
{
if (x%p==0) pr[i].push_back(p);
while (x%p==0) x/=p;
}
if (x>1) pr[i].push_back(x);
}
for (int i=0;i<n;i++)
for (int p:pr[a[i]]) add(p,i);
for (int i=0;i<n;i++)
{
int l=i, r=i;
for (int p:pr[a[i]])
{
auto it=rng[p].upper_bound({i+1,0});it--;
l=min(l,it->first), r=max(r,it->second);
}
if (a[i]==1) l++, r--;
modify(i,i+1,l,0), modify(i,i+1,r,1);
}
for (auto e:v)
{
if (e[0]==1)
{
int id=e[1], x=e[2];
int l=get(id,id+1,0), r=get(id,id+1,1);
modify(l,id,id-1,1), modify(id+1,r+1,id+1,0);
for (int p:pr[a[id]]) rem(p,id);
vector<pair<int,int>> v;
for (int p:pr[x])
{
add(p,id);
auto it=rng[p].upper_bound({id+1,0});it--;
v.push_back(*it);
}
sort(v.begin(),v.end());
int pv=-1;
for (auto [l,r]:v)
if (r>pv) modify(l,id+1,r,1), pv=r;
pv=n;
reverse(v.begin(),v.end());
for (auto [l,r]:v)
if (l<pv) modify(id,r+1,l,0), pv=l;
a[id]=x;
if (x==1)
modify(id,id+1,id+1,0), modify(id,id+1,id-1,1);
}
else
{
int l=e[1], r=e[2];
if (get(e[0],e[0]+1,0)>=r-1)
{
cout<<1ll*(r-l+2)*(r-l+1)/2<<endl;
continue;
}
cout<<val(l,r,1)-val(r,n,0)+val(r,n,1)<<endl;
}
}
return 0;
}
