#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) { // cout<<"AT "<<x<<' '<<v<<endl; int lst=x-1,gt=0; while(lst<=n and gt!=1) { 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; } // compute minimum l such that [l,s] has same gcd as [x,s] { int s=0,e=x; while(s+1<e) { int mid=(s+e)/2; if(get(mid,r)==get(x,r)) { e=mid; } else{ s=mid; } } l=e; } // cout<<l<<' '<<r<<' '<<lst<<' '<<gt<<endl; // 1. [l,x] we update max equal r // 2. [l,x] we update set equal r for(int jp=l;jp<=x;jp++) { rp[jp]=r; } lst=r+1; gt=get(x,lst); // x=r+1; } } 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); // compute all index where the gcd(x,index) changes fixit(x,v); if(x>1) fixit(x-1,a[x-1]); } 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; } } }