#include <bits/stdc++.h> using namespace std; // #define int long long #define ll long long const int N=1e5+10; int a[N],seg[4*N],n,q,rp[N],lzy[4*N]; ll seg2[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) return; if(ql<=l and r<=qr){ lzy[d]=v; push(l,r,d); 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]; } 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) 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; } } Set(e,lst1,r); lst1=e-1; gt1=get(lst1,r); } } Set(x,x,r); lst=r+1; gt=get(x,lst); } } long long f(int x) { return (1ll*x*(x+1))/2; } int32_t 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]); } 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; 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; e--; ans+=getSum(l,e); ans+=(e-l+1); ans-=(f(e)-f(l-1)); cout<<ans<<'\n'; } } }