#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;
int a[N],seg[4*N],n,q,rp[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 fixit(int x,int v) // lg^4 1e9 tight
{
// cout<<"AT "<<x<<' '<<v<<endl;
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;
}
}
//[e,lst1] = r
for(int j=e;j<=lst1;j++)rp[j]=r;
lst1=e-1;
gt1=get(lst1,r);
}
}
rp[x]=r;
lst=r+1;
gt=get(x,lst);
}
}
long long f(int x)
{
return (1ll*x*(x+1))/2;
}
int 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]--;
}
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;
long long ans=0;
// rp is sorted easy to binary serach
//
{
int s=l-1,e=r+1;
while(s+1<e)
{
int mid=(s+e)/2;
if(rp[mid]>=r)
{
e=mid;
}
else{
s=mid;
}
}
int c=r+1-e;
ans+= 1ll*r*c - (f(r)-f(r-c)) + c;
for(int i=l;i<e;i++)
{
ans+=rp[i]-i+1;
}
}
cout<<ans<<endl;
}
}
}
