#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
const int N=1e5+10;
int a[N],seg[4*N],n,q,rp[N],seg2[4*N],lzy[4*N];
void update(int &i,int &v,int l=1,int r=n,int d=1)
{
if(i<l or r<i)return;
if(l==r)
{
seg[d]=a[i]=v;
return;
}
int m=(l+r)>>1,cl=d<<1,cr=cl|1;
update(i,v,l,m,cl);
update(i,v,m+1,r,cr);
seg[d]=__gcd(seg[cl],seg[cr]);
}
int get(int ql,int qr,int l=1,int r=n,int d=1)
{
if(qr<l or r<ql) return 0;
if(ql<=l and r<=qr) return seg[d];
int m=(l+r)>>1,cl=d<<1,cr=cl|1;
return __gcd(get(ql,qr,l,m,cl),get(ql,qr,m+1,r,cr));
}
void push(int l,int r,int v)
{
if(lzy[v]!=0)
{
seg2[v]=1ll*(r-l+1)*lzy[v];
if(l!=r)
{
lzy[v*2]=lzy[2*v+1]=lzy[v];
}
lzy[v]=0;
}
}
void Set(int ql,int qr,int v,int l=1,int r=n,int d=1)
{
push(l,r,d);
if(qr<l or r<ql){
// cout<<"AT "
// cout<<"At1 "<<d<<' '<<l<<' '<<r<<' '<<" SM = "<<seg2[d]<<endl;
return;
}
if(ql<=l and r<=qr){
lzy[d]=v;
push(l,r,d);
// cout<<"At2 "<<d<<' '<<l<<' '<<r<<' '<<" SM = "<<seg2[d]<<endl;
return;
}
int m=(l+r)>>1,cl=d<<1,cr=cl|1;
Set(ql,qr,v,l,m,cl);
Set(ql,qr,v,m+1,r,cr);
seg2[d]=seg2[cl]+seg2[cr];
// cout<<"At3 "<<d<<' '<<l<<' '<<r<<' '<<" SM = "<<seg2[d]<<endl;
}
int getSum(int ql,int qr,int l=1,int r=n,int d=1)
{
push(l,r,d);
if(qr<l or r<ql) return 0;
if(ql<=l and r<=qr)
{
// cout<<"AT "<<l<<' '<<r<<' '<<seg2[d]<<endl;
return seg2[d];
}
int m=(l+r)>>1,cl=d<<1,cr=cl|1;
return (getSum(ql,qr,l,m,cl)+getSum(ql,qr,m+1,r,cr));
}
void fixit(int x,int v) // lg^4 1e9 tight
{
int lst=x-1,gt=0;
while(lst<=n and gt!=1) // lg(1e9)
{
int l,r;
{
int s=lst,e=n+1;
while(s+1<e)
{
int mid=(s+e)/2;
if(get(x,mid)==gt)
{
s=mid;
}
else{
e=mid;
}
}
r=s;
}
{
int lst1=x-1,gt1=__gcd(gt,a[x-1]);
while(lst1>=1 and gt1!=1) // O(lg 1e9)
{
int s=0,e=lst1;
while(s+1<e)
{
int mid=(s+e)/2;
if(get(mid,r)==gt1)
{
e=mid;
}
else{
s=mid;
}
}
// cout<<"Setting "<<e<<' '<<lst1<<' '<<r<<endl;
Set(e,lst1,r);
lst1=e-1;
gt1=get(lst1,r);
}
}
Set(x,x,r);
// cout<<"Setting "<<x<<' '<<x<<' '<<r<<endl;
lst=r+1;
gt=get(x,lst);
}
}
long long f(int x)
{
return (1ll*x*(x+1))/2;
}
int32_t main()
{
ios::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
update(i,a[i]);
}
for(int i=n;i>=1;i--)
{
rp[i]=(i==n)?n:rp[i+1];
while(rp[i]>=i and get(i,rp[i])==1)rp[i]--;
Set(i,i,rp[i]);
}
// Build();
while(q--)
{
int t;
cin>>t;
if(t==1)
{
int x,v;
cin>>x>>v;
update(x,v);
fixit(x,v);
}
else
{
int l,r;
cin>>l>>r;
// for(int i=1;i<=n;i++)
// {
// cout<<getSum(i,i)<<' ';
// }
// cout<<endl;
long long ans=0;
{
int s=l-1,e=r+1;
while(s+1<e)
{
int mid=(s+e)/2;
if(getSum(mid,mid)>=r)
{
e=mid;
}
else{
s=mid;
}
}
int c=r+1-e;
ans+= 1ll*r*c - (f(r)-f(r-c)) + c;
ans+=getSum(l,e-1);
ans+=(e-l);
ans-=(f(e-1)-f(l-1));
// cout<<l<<' '<<e-1<<endl;
// cout<<getSum(l,e-1)<<' '<<(e-l)<<' '<<(f(e-1)-f(l-1))<<endl;
}
// for(int i=1;i<=n;i++)
// {
// cout<<getSum(i,i)<<' ';
// }
// cout<<endl;
cout<<ans<<endl;
}
}
}
