#pragma GCC optimize("O2") #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; #define ll long long int const N=1e5+10; int gc[4*N]={}; int a[N]={}; int n,q; struct node { int mn=1e9; ll sm=0; int lazy=-1; }; node seg[4*N]={}; node merge(node a,node b) { node c; c.sm=a.sm+b.sm; c.mn=min(a.mn,b.mn); c.lazy=-1; return c; } 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)); } 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; } 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); seg[i]=merge(seg[i*2],seg[i*2+1]); } node dm; node get1(int l,int r,int i=1,int st=0,int en=n-1) { if (st>=l&&en<=r) return seg[i]; if (st>r||en<l) return dm; int mid=(st+en)/2; if (seg[i].lazy!=-1) push(i,st,en); return merge(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; int a[n]; for (auto& i:a) cin>>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(j,i); if (gc==1) break; int st=-1,en=j; while (st+1<en) { int mid=(st+en)/2; if (get(mid,j)==gc) en=mid; else st=mid; } int ind=en; 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; if (get1(mid,j).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; if (get1(mid,r).mn>r) en=mid; else st=mid; } ll f=get1(l,st).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(); } }