#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],seg[4*N],n,q;
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));
}
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]);
}
while(q--)
{
int t;
cin>>t;
if(t==1) // O(lg n)
{
int x,v;
cin>>x>>v;
update(x,v);
}
else// O(n lg^2 n)
{
int l,r;
cin>>l>>r;
int k=r;
long long ans=0;
for(int i=r;i>=l;i--)
{
while(get(i,k)==1)k--;
ans+=k-i+1;
}
cout<<ans<<endl;
}
}
}
