#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e5+1;
int gc[3*N]={};
int a[N]={};
int n,q;
struct node
{
int mn=1e9;
ll sm=0;
int lazy=-1;
};
node seg[3*N]={};
inline void merge(node a,node b,node& c)
{
c.sm=a.sm+b.sm;
c.mn=min(a.mn,b.mn);
c.lazy=-1;
}
void update(int r,int vl,int i=1,int st=0,int en=n-1)
{
if (st==en)
{
gc[i]=vl;return;
}
int mid=(st+en)/2;
if (r<=mid)
update(r,vl,i*2,st,mid);
else
update(r,vl,i*2+1,mid+1,en);
gc[i]=__gcd(gc[i*2],gc[i*2+1]);
}
int get(int l,int r,int i=1,int st=0,int en=n-1)
{
if (st>=l&&en<=r)
return gc[i];
if (st>r||en<l)
return 0;
int mid=(st+en)/2;
return __gcd(get(l,r,i*2,st,mid),get(l,r,i*2+1,mid+1,en));
}
inline void push(int i,int st,int en)
{
int mid=(st+en)/2;
int lc=i*2,rc=lc+1;
int vl=seg[i].lazy;
seg[lc].lazy=seg[i].lazy;
seg[lc].mn=vl;
seg[lc].sm=1ll*vl*(mid-st+1);
seg[rc].lazy=seg[i].lazy;
seg[rc].mn=vl;
seg[rc].sm=1ll*vl*(en-mid);
seg[i].lazy=-1;
}
void upd(int l,int r,int vl,int i=1,int st=0,int en=n-1)
{
if (l>r)
return ;
if (st>=l&&en<=r)
{
seg[i].lazy=vl;
seg[i].mn=vl;
seg[i].sm=1ll*vl*(en-st+1);
return;
}
if (st>r||en<l)
return;
if (seg[i].lazy!=-1)
push(i,st,en);
int mid=(st+en)/2;
upd(l,r,vl,i*2,st,mid);upd(l,r,vl,i*2+1,mid+1,en);
merge(seg[i*2],seg[i*2+1],seg[i]);
}
node dm;
node cur;
void get1(int l,int r,int i=1,int st=0,int en=n-1)
{
if (st==0&&en==n-1)
cur=dm;
if (st>=l&&en<=r)
{
merge(seg[i],cur,cur);
return;
}
if (st>r||en<l)
return;
int mid=(st+en)/2;
if (seg[i].lazy!=-1)
push(i,st,en);
get1(l,r,i*2,st,mid);get1(l,r,i*2+1,mid+1,en);
}
ll f(ll x)
{
return (x*(x+1))/2;
}
ll gd(ll l,ll r)
{
return f(r)-f(l-1);
}
inline void solve()
{
cin>>n>>q;
int a[n];
for (auto& i:a)
cin>>i;
for (int i=0;i<n;i++)
update(i,a[i]);
for (int i=0;i<n;i++)
{
int st=i,en=n;
while (st+1<en)
{
int mid=(st+en)/2;
if (get(i,mid)>1)
st=mid;
else
en=mid;
}
if (a[i]==1)
st=i-1;
upd(i,i,st);
}
while (q--)
{
int ty;
cin>>ty;
if (ty==1)
{
int i,v;
cin>>i>>v;
i--;
if (a[i]==v) continue;
a[i]=v;
update(i,v);
int j=i;
int gc=0;
int mx=n-1;
while (j>=0)
{
gc=__gcd(a[j],gc);
if (gc==1)
break;
int st=-1,en=j;
while (st+1<en)
{
int mid=(st+en)/2;
if (get(mid,j)==gc)
en=mid;
else
st=mid;
}
int ind=en;
st=ind,en=mx+1;
while (st+1<en)
{
int mid=(st+en)/2;
if (get(ind,mid)>1)
st=mid;
else
en=mid;
}
mx=st;
upd(ind,j,st);
j=ind-1;
}
int st=-1,en=j+1;
while (st+1<en)
{
int mid=(st+en)/2;
get1(mid,j);
if (cur.mn>=i)
en=mid;
else
st=mid;
}
upd(en,j,i-1);
}
else
{
int l,r;
cin>>l>>r;
l--;r--;
int st=l-1,en=r+1;
while (st+1<en)
{
int mid=(st+en)/2;
get1(mid,r);
if (cur.mn>r)
en=mid;
else
st=mid;
}
get1(l,st);
ll f=cur.sm;
f+=1ll*(r-en+1)*(r);
f-=gd(l,r);
f+=(r-l+1);
cout<<f<<'\n';
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t=1;
for (int i=1;i<=t;i++)
{
solve();
}
}
