#include <bits/stdc++.h>
// #include <numeric>
using namespace std;
const int N=1e5+10,LG=17;
int a[N],gd[N][LG],n,q,rp[N];
int get(int l,int r)
{
int g=__lg(r-l+1);
return __gcd(gd[l][g],gd[r-(1<<g)+1][g]);
}
void compute()
{
for(int i=1;i<=n;i++)gd[i][0]=a[i];
for(int j=1;j<LG;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
gd[i][j]=__gcd(gd[i][j-1],gd[i+(1<<(j-1))][j-1]);
}
}
rp[n+1]=n;
for(int i=n;i>=1;i--)
{
rp[i]=rp[i+1];
// cout<<i<<' '<<rp[i]<<' '<<get(i,rp[i])<<endl;
while(rp[i]>=i and get(i,rp[i])==1)rp[i]--;
}
// for(int i=1;i<=n;i++)cout<<rp[i]<<' ';
// cout<<endl;
}
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];
}
compute();
while(q--)
{
int t;
cin>>t;
if(t==1)
{
int x,v;
cin>>x>>v;
a[x]=v;
compute();
}
else
{
int l,r;
cin>>l>>r;
long long ans=0;
for(int i=l;i<=r;i++)
ans+=min(rp[i],r)-i+1;
cout<<ans<<endl;
}
}
}
