#include <bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N],seg[4*N],n,q; 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)); } 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]); } while(q--) { int t; cin>>t; if(t==1) // O(lg n) { int x,v; cin>>x>>v; update(x,v); } else// O(n lg^2 n) { int l,r; cin>>l>>r; int k=r; long long ans=0; for(int i=r;i>=l;i--) { while(get(i,k)==1)k--; ans+=k-i+1; } cout<<ans<<endl; } } }