#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],seg2[4*N],lzy[4*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 push(int l,int r,int v) { if(lzy[v]!=0) { seg2[v]=1ll*(r-l+1)*lzy[v]; if(l!=r) { lzy[v*2]=lzy[2*v+1]=lzy[v]; } lzy[v]=0; } } void Set(int ql,int qr,int v,int l=1,int r=n,int d=1) { push(l,r,d); if(qr<l or r<ql){ // cout<<"AT " // cout<<"At1 "<<d<<' '<<l<<' '<<r<<' '<<" SM = "<<seg2[d]<<endl; return; } if(ql<=l and r<=qr){ lzy[d]=v; push(l,r,d); // cout<<"At2 "<<d<<' '<<l<<' '<<r<<' '<<" SM = "<<seg2[d]<<endl; return; } int m=(l+r)>>1,cl=d<<1,cr=cl|1; Set(ql,qr,v,l,m,cl); Set(ql,qr,v,m+1,r,cr); seg2[d]=seg2[cl]+seg2[cr]; // cout<<"At3 "<<d<<' '<<l<<' '<<r<<' '<<" SM = "<<seg2[d]<<endl; } int getSum(int ql,int qr,int l=1,int r=n,int d=1) { push(l,r,d); if(qr<l or r<ql) return 0; if(ql<=l and r<=qr) { // cout<<"AT "<<l<<' '<<r<<' '<<seg2[d]<<endl; return seg2[d]; } int m=(l+r)>>1,cl=d<<1,cr=cl|1; return (getSum(ql,qr,l,m,cl)+getSum(ql,qr,m+1,r,cr)); } void fixit(int x,int v) // lg^4 1e9 tight { 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; } } // cout<<"Setting "<<e<<' '<<lst1<<' '<<r<<endl; Set(e,lst1,r); lst1=e-1; gt1=get(lst1,r); } } Set(x,x,r); // cout<<"Setting "<<x<<' '<<x<<' '<<r<<endl; 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]--; Set(i,i,rp[i]); } // Build(); 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; // for(int i=1;i<=n;i++) // { // cout<<getSum(i,i)<<' '; // } // cout<<endl; long long ans=0; { int s=l-1,e=r+1; while(s+1<e) { int mid=(s+e)/2; if(getSum(mid,mid)>=r) { e=mid; } else{ s=mid; } } int c=r+1-e; ans+= 1ll*r*c - (f(r)-f(r-c)) + c; ans+=getSum(l,e-1); ans+=(e-l); ans-=(f(e-1)-f(l-1)); // cout<<l<<' '<<e-1<<endl; // cout<<getSum(l,e-1)<<' '<<(e-l)<<' '<<(f(e-1)-f(l-1))<<endl; } // for(int i=1;i<=n;i++) // { // cout<<getSum(i,i)<<' '; // } // cout<<endl; cout<<ans<<endl; } } }