#include <bits/stdc++.h> using namespace std; #define endl '\n' #define ll long long #define int long long const int M = 1e5 + 1; ll seg[M*2][2], lz[M*2][2]; map<int,set<pair<int,int>>> rng; void push(int v,int s,int e,int i) { int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2; seg[lc][i]=(mid-s)*lz[v][i], lz[lc][i]=lz[v][i]; seg[rc][i]=(e-mid)*lz[v][i], lz[rc][i]=lz[v][i]; lz[v][i]=-1; } void modify(int l,int r,int x,int i,int v=0,int s=0,int e=M) { if (l>=e or r<=s) return; if (l<=s && e<=r) { lz[v][i]=x; seg[v][i]=(e-s)*lz[v][i]; return; } int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2; if (~lz[v][i]) push(v,s,e,i); modify(l,r,x,i,lc,s,mid); modify(l,r,x,i,rc,mid,e); seg[v][i]=seg[lc][i]+seg[rc][i]; } ll get(int l,int r,int i,int v=0,int s=0,int e=M) { if (l>=e or r<=s) return 0; if (l<=s && e<=r) return seg[v][i]; int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2; if (~lz[v][i]) push(v,s,e,i); return get(l,r,i,lc,s,mid)+get(l,r,i,rc,mid,e); } void add(int x,int i) { auto it=rng[x].upper_bound({i,0}); pair<int,int> pv={-1,-1}, nx={-1,-1}; if (it!=rng[x].end()) nx=*it; if (it!=rng[x].begin()) it--, pv=*it; if (~pv.first && ~nx.first && pv.second+2==nx.first) { rng[x].erase(pv), rng[x].erase(nx); rng[x].insert({pv.first,nx.second}); } else if(~pv.first && pv.second==i-1) rng[x].erase(pv), pv.second++, rng[x].insert(pv); else if(~nx.first && nx.first==i+1) rng[x].erase(nx), nx.first--, rng[x].insert(nx); else rng[x].insert({i,i}); } void rem(int x,int i) { auto it=rng[x].upper_bound({i+1,0}); it--; pair<int,int> p=*it; rng[x].erase(it); if (p.first!=i) rng[x].insert({p.first,i-1}); if (p.second!=i) rng[x].insert({i+1,p.second}); } ll val(ll l,ll r,int i) { int x=get(l,r,i)-r*(r-1)/2+l*(l-1)/2; if (!i) x*=-1; return x+r-l; } signed main() { ios::sync_with_stdio(0); cin.tie(NULL), cout.tie(NULL); for (int i=0;i<M*2;i++) lz[i][0]=lz[i][1]=-1; int n,q; cin>>n>>q; set<int> se; int a[n]; for (int i=0;i<n;i++) cin>>a[i], se.insert(a[i]); vector<array<int,3>> v; while (q--) { int t, l, r; cin>>t>>l>>r; l--; v.push_back({t,l,r}); if (t==1) se.insert(r); } map<int,vector<int>> pr; for (int i:se) { int x=i; for (int p=2;p*p<=x;p+=1+p%2) { if (x%p==0) pr[i].push_back(p); while (x%p==0) x/=p; } if (x>1) pr[i].push_back(x); } for (int i=0;i<n;i++) for (int p:pr[a[i]]) add(p,i); for (int i=0;i<n;i++) { int l=i, r=i; for (int p:pr[a[i]]) { auto it=rng[p].upper_bound({i+1,0});it--; l=min(l,it->first), r=max(r,it->second); } if (a[i]==1) l++, r--; modify(i,i+1,l,0), modify(i,i+1,r,1); } for (auto e:v) { if (e[0]==1) { int id=e[1], x=e[2]; int l=get(id,id+1,0), r=get(id,id+1,1); modify(l,id,id-1,1), modify(id+1,r+1,id+1,0); for (int p:pr[a[id]]) rem(p,id); vector<pair<int,int>> v; for (int p:pr[x]) { add(p,id); auto it=rng[p].upper_bound({id+1,0});it--; v.push_back(*it); } sort(v.begin(),v.end()); int pv=-1; for (auto [l,r]:v) if (r>pv) modify(l,id+1,r,1), pv=r; pv=n; reverse(v.begin(),v.end()); for (auto [l,r]:v) if (l<pv) modify(id,r+1,l,0), pv=l; a[id]=x; if (x==1) modify(id,id+1,id+1,0), modify(id,id+1,id-1,1); } else { int l=e[1], r=e[2]; if (get(e[0],e[0]+1,0)>=r-1) { cout<<1ll*(r-l+2)*(r-l+1)/2<<endl; continue; } cout<<val(l,r,1)-val(r,n,0)+val(r,n,1)<<endl; } } return 0; }