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