#pragma GCC optimize("O2") #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #include <bits/stdc++.h> using namespace std; #define ll long long int const N=1e5+1; int gc[3*N]={}; int a[N]={}; int n,q; struct node { int mn=1e9; ll sm=0; int lazy=-1; }; node seg[3*N]={}; inline void merge(node a,node b,node& c) { c.sm=a.sm+b.sm; c.mn=min(a.mn,b.mn); c.lazy=-1; } void update(int r,int vl,int i=1,int st=0,int en=n-1) { if (st==en) { gc[i]=vl;return; } int mid=(st+en)/2; if (r<=mid) update(r,vl,i*2,st,mid); else update(r,vl,i*2+1,mid+1,en); gc[i]=__gcd(gc[i*2],gc[i*2+1]); } int get(int l,int r,int i=1,int st=0,int en=n-1) { if (st>=l&&en<=r) return gc[i]; if (st>r||en<l) return 0; int mid=(st+en)/2; return __gcd(get(l,r,i*2,st,mid),get(l,r,i*2+1,mid+1,en)); } inline void push(int i,int st,int en) { int mid=(st+en)/2; int lc=i*2,rc=lc+1; int vl=seg[i].lazy; seg[lc].lazy=seg[i].lazy; seg[lc].mn=vl; seg[lc].sm=1ll*vl*(mid-st+1); seg[rc].lazy=seg[i].lazy; seg[rc].mn=vl; seg[rc].sm=1ll*vl*(en-mid); seg[i].lazy=-1; } int wlk(int l,int r,int vl,int i=1,int st=0,int en=n-1) { if (st>=l&&en<=r) { if (__gcd(gc[i],vl)==vl) return st; if (__gcd(a[en],vl)!=vl) return n+10; } if (st>r||en<l) return n; int mid=(st+en)/2; int z=wlk(l,r,vl,i*2+1,mid+1,en); if (z==mid+1||z==n) z=min(z,wlk(l,r,vl,i*2,st,mid)); return z; } void upd(int l,int r,int vl,int i=1,int st=0,int en=n-1) { if (l>r) return ; if (st>=l&&en<=r) { seg[i].lazy=vl; seg[i].mn=vl; seg[i].sm=1ll*vl*(en-st+1); return; } if (st>r||en<l) return; if (seg[i].lazy!=-1) push(i,st,en); int mid=(st+en)/2; upd(l,r,vl,i*2,st,mid);upd(l,r,vl,i*2+1,mid+1,en); merge(seg[i*2],seg[i*2+1],seg[i]); } node dm; node cur; void get1(int l,int r,int i=1,int st=0,int en=n-1) { if (st==0&&en==n-1) cur=dm; if (st>=l&&en<=r) { merge(seg[i],cur,cur); return; } if (st>r||en<l) return; int mid=(st+en)/2; if (seg[i].lazy!=-1) push(i,st,en); get1(l,r,i*2,st,mid);get1(l,r,i*2+1,mid+1,en); } ll f(ll x) { return (x*(x+1))/2; } ll gd(ll l,ll r) { return f(r)-f(l-1); } inline void solve() { cin>>n>>q; for (int i=0;i<n;i++) cin>>a[i]; for (int i=0;i<n;i++) update(i,a[i]); for (int i=0;i<n;i++) { int st=i,en=n; while (st+1<en) { int mid=(st+en)/2; if (get(i,mid)>1) st=mid; else en=mid; } if (a[i]==1) st=i-1; upd(i,i,st); } while (q--) { int ty; cin>>ty; if (ty==1) { int i,v; cin>>i>>v; i--; if (a[i]==v) continue; a[i]=v; update(i,v); int j=i; int gc=0; int mx=n-1; while (j>=0) { gc=__gcd(a[j],gc); if (gc==1) break; int ind=wlk(0,j,gc); int st=ind,en=mx+1; while (st+1<en) { int mid=(st+en)/2; if (get(ind,mid)>1) st=mid; else en=mid; } mx=st; upd(ind,j,st); j=ind-1; } int st=-1,en=j+1; while (st+1<en) { int mid=(st+en)/2; get1(mid,j); if (cur.mn>=i) en=mid; else st=mid; } upd(en,j,i-1); } else { int l,r; cin>>l>>r; l--;r--; int st=l-1,en=r+1; while (st+1<en) { int mid=(st+en)/2; get1(mid,r); if (cur.mn>r) en=mid; else st=mid; } get1(l,st); ll f=cur.sm; f+=1ll*(r-en+1)*(r); f-=gd(l,r); f+=(r-l+1); cout<<f<<'\n'; } } } signed main() { ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); int t=1; for (int i=1;i<=t;i++) { solve(); } }