#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; } } }